# How many 6-digit numbers have distinct digits but no consecutive digits both odd?

How many 6-digit natural numbers exist with the distinct digits and two arbitrary consecutive digits can not be simultaneously odd numbers?
I have tried to set up recurrence relation , by considering a valid 5 digit number satisfying the property and then appending the required digit at the last place to produce valid 6 digit number , but things are getting cumbersome. Is there a nice alternative solution? Thanks in advance.

• I suppose a leading zero is not allowed, as in 098765? Commented Sep 11, 2017 at 16:25
• @JeppeStigNielsen Yes leading zero is not allowed.
– rugi
Commented Sep 11, 2017 at 16:29
• Are you asking how many six-digit positive integers with distinct digits do not have consecutive odd digits? Commented Sep 11, 2017 at 16:39
• I'd do it in cases, from the number of odd digits. The most you can have is $3$, as in $OEOEOE, EOEOEO$. Easy to count each pattern.
– lulu
Commented Sep 11, 2017 at 16:40
• Just to be clear: I didn't mean to suggest that the patterns I gave for three odds are all the cases with three odds. They aren't. There are also $OEEOEO, OEOEEO$.
– lulu
Commented Sep 11, 2017 at 16:51

One way to do it is by looking at cases, as @lulu suggested. There are $3$ basic cases: $1$ odd number, $2$ odd numbers or $3$ odd numbers. I'll go through each case below, splitting each case into scenarios starting with an odd number (O) and scenarios starting with an even number (E). The reason for this split is that scenarios starting with an even number are not allowed to start with a zero and therefore differ slightly in the computation.

Case 1

With $1$ odd number you have the following possible scenarios

(a) OEEEEE

(b) EOEEEE, EEOEEE, EEEOEE, EEEEOE, EEEEEO

The number of combinations $n_1$ for this case is $$n_1 = \binom{5}{1} \cdot \binom{5}{5} \cdot 5! + 5 \cdot \binom{4}{1} \cdot \binom{5}{1} \cdot \binom{4}{4} \cdot 4! = 3,000$$

Case 2

With $2$ odd numbers you have the following possible scenarios

(a) OEOEEE, OEEOEE, OEEEOE, OEEEEO

(b) EOEOEE, EOEEOE, EOEEEO, EEOEOE, EEOEEO, EEEOEO

The number of combinations $n_2$ for this case is $$n_2 = 4 \cdot \binom{5}{2} \cdot 2! \cdot \binom{5}{4} \cdot 4! + 6 \cdot \binom{4}{1} \cdot \binom{5}{2} \cdot 2! \cdot \binom{4}{3} \cdot 3! = 21,120$$ Case 3

With $3$ odd numbers you have the following possible scenarios

(a) OEOEOE, OEOEEO, OEEOEO

(b) EOEOEO

The number of combinations $n_3$ for this case is $$n_3 = 3 \cdot \binom{5}{3} \cdot 3! \cdot \binom{5}{3} \cdot 3! + \binom{4}{1} \cdot \binom{5}{3} \cdot 3! \cdot \binom{4}{2} \cdot 2! = 13,680$$

In conclusion

The total number of combinations is then $N= n_1 + n_2 + n_3$ or $$N = 3,000 + 21,120 + 13,680 = 37,800$$

which matches the number found by @Jeppe in the comments.