Simple question on multinomial theorem

How many natural numbers less than ${10^8}$ are there,whose sum of digits equals ${7}$?

My Try: I used multinomial theorem to solve it and I am getting an answer of 1716. I want to know whether I am correct or not. Please help me as I have no way other than this to check my answer. Thank you! :))

-
See partitions. –  Lucian Apr 29 '14 at 11:19
@Lucian: Sorry, but I am unable to understand how to use partitions to solve it. Can you please demonstrate? Thank you :)) –  Abir Mukherjee Apr 29 '14 at 11:41
Well, your question is related to determining the number of partitions of $7$, is it not ? –  Lucian Apr 29 '14 at 12:06

As Lucian commented, this question can be approached with partitions:

Note:

The partitions (order immaterial) of 7 number 15.

Also, at most, 7 can be partitioned into 7 integers (1+1+1+…). Also, fortunately, $n<10^8$ has 8 "slots" (the question would be a bit different if, say, the cap was $10^5$)

Now, some additional combinatorics comes in.

For any given partition of 7, say 4 + 2 + 1, there will be a corresponding amount of $0$s (as you need to fill up all 8 "slots".

Hence for the case of 4, 2, 1 and an additional 5 $0$s, we need to figure out the number of combinations, as this represents all the different integers up to $10^8$ with the said digits in them.

So we would have: $8!/(1!*1!*1!*5!)$

(there is the link to multinomials!)

Repeat this process for the 14 other partitions of 7, and there you have your answer

-

You seek the number of solutions of

$$a_!+a_2...a_8=7$$

We have all of them as whole numbers.(We need not worry about the trivial case $0$). Also, you need not worry about their upper limit of $9$ for obvious reasons.

Now define $A_i=a_i+1$

Now you have :

$$\sum A_i=7+8=15$$

Note that this does not affect number of solutions. Now write $15$ as $1+1+1..._{15\text{ times}}$

Now as $A_i\in \Bbb N$ you can choose any $7$ $+$ plus signs on the right and partition your $A_is$ into one of your solutions. Number of ways : Choose $7$ plus signs from $14$ plus signs on $RHS$.

$$^{14}C_7$$

-