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

Question

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.

Answer 1

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.