Find the number of 6-digit odd numbers that do not contain two consecutive fours. Find the number of 6-digit odd numbers that do not contain two consecutive fours.
I tried to break it into some cases that if the tens digit is 4 or not(since the units digit has to be an odd number), then I got a big tree. Is that any short cut to solve this problem?
 A: This is an inclusion-exclusion problem.  Let $U$ denote the set of all 6-digit odd numbers.  Let $A_1\subseteq U$ denote those for which the first two digits are 4.  Let $A_2\subseteq U $ denote those for which the second and third digits are 4.  Let $A_3\subseteq U$ denote those for which the third and fourth digits are $4$.  Let $A_4\subseteq U$ denote those for which the fourth and fifth digits are $4$.  The sixth digit is odd, so can never be 4.  What you want is $|U|-|A_1\cup A_2\cup A_3\cup A_4|$, which can be computed as $$|U|-|A_1|-|A_2|-|A_3|-|A_4|+|A_1\cap A_2|+\cdots+|A_3\cap A_4|-|A_1\cap A_2\cap A_3|-|A_1\cap A_2\cap A_4|-|A_1\cap A_3\cap A_4|-|A_2\cap A_3\cap A_4|+|A_1\cap A_2\cap A_3\cap A_4|$$
Let me know if you have trouble computing any of these; there will be lots of repetition so it's not as hard as it looks.
A: $9\times10^4\times5=$ total ways to arrange a six-digit odd number
$10^3\times5=$ ways to arrange a six-digit odd number starting with two consecutive 4's
(e.g. 445913)
$3=$ ways to choose two consecutive 4's from the middle four digits
$9\times10^2\times3\times5=$ ways to arrange a six-digit odd number with two consecutive 4's placed in the middle four digits
(e.g. 514493, 351447)
answer:
$(9\times10^4\times5) - (10^3\times5) - (9\times10^2\times3\times5)$
