How many numbers smaller than $10^6$ contain exactly three '$9$'s and have an odd sum of digits?

An alternative method:

Choose the three locations for the $9$s: there are $\dbinom 63$ possibilities.

Then, among the remaining digits (not $9$s), choose any digit except $9$ for the leftmost place ($9$ possibilities), then choose any digit except $9$ for the middle place ($9$ possibilities).

Among the ways to fill these two digits, there are $4^2 + 5^2$ in which we choose two digits of the same parity and get an even sum, in which case we need to choose an even digit for the last open place ($5$ choices). There are $2\times4\times 5$ ways in which to get an odd sum, in which case we need one more odd digit ($4$ choices, since $9$ is excluded).

So altogether we have $$ \binom 63 \left(5(4^2 + 5^2) + 4(2\times4\times 5) \right) = 7300. $$

With your idea:

• Three even digits and the 9:

  • The same even digit every time (5 choices: $0, 2, 4, 6, 8$ and permutation): $5 \cdot \frac{6!}{3! \cdot 3!}$
  • Two even digits are the same: $5 \cdot 4 \cdot \frac{6!}{3! \cdot 2!}$
  • The three even digits are different: $5 \cdot 4 \cdot 3 \cdot \frac{6!}{3!}$

• Two odd digits, one even (4 choices for the odd digit: $1, 3, 5, 7$):

  • The same odd digit : $\underbrace{5}_{even} \cdot \underbrace{4}_{odd} \cdot \frac{6!}{3! \cdot 2!}$
  • Odd digits are different: $\underbrace{5}_{even} \cdot \underbrace{4 \cdot 3}_{odd} \cdot \frac{6!}{3!}$

The answer is the sum of all cases.

There are $\frac{6!}{3!3!}$ to choose where the 9's are and where the even numbers are. However, even if we know that the three even numbers are equal, there are $5$ ways to choose if it is $0,2,4,6$ or $8$. (Note that we don't care about leading zeros, because they don't affect the sum of digits.) So there are $5\frac{6!}{3!3!}$ such ways. When we have two different even numbers, surely there is $\frac{6!}{3!2!}$ ways to separate 9's positions, and two even number positions, but there are also $5*4=20$ ways to choose actual even numbers. In the case of different even numbers we have $5*4*3=60$ ways to choose even numbers for the first, second and third non-9 digit and $\frac{6!}{3!3!}$ ways to choose 9's places before. So in the case of even digits there are $$5\frac{6!}{3!3!}+20\frac{6!}{3!2!}+60\frac{6!}{3!3!}=\frac{6!}{3!}(5/6+10+10)=20*(5+60+60)=2500$$ However, note that in fact separating three cases doesn't give any advantage to us. We would better say that there is $\frac{6!}{3!3!}$ ways to choose the places of $9$'s and then $5^3$ ways to choose even numbers for other three places: just five choices for each place, independently from the others. And we obtain $$125\frac{6!}{3!3!}=4*5^4=2500$$ The same, all is ok.

For the case of two odds we can do the following: choose 9s places in $\frac{6!}{3!3!}$ ways, then choose in 3 ways where is even and in 5 ways what is it. For two odds we can choose out of $1,3,5,7$, so we have $4^2$ choices. All in all, for the odd case, $$\frac{6!}{3!3!}*3*5*16=20*15*16=4800$$ And finally, $2500+4800=7300$ is the answer.