# 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? – Jeppe Stig Nielsen Sep 11 '17 at 16:25
• @JeppeStigNielsen Yes leading zero is not allowed. – rugi Sep 11 '17 at 16:29
• Are you asking how many six-digit positive integers with distinct digits do not have consecutive odd digits? – N. F. Taussig Sep 11 '17 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 Sep 11 '17 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 Sep 11 '17 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.