Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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! :))

share|improve this question
    
See partitions. –  Lucian Apr 29 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 at 11:41
1  
Well, your question is related to determining the number of partitions of $7$, is it not ? –  Lucian Apr 29 at 12:06

2 Answers 2

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

share|improve this 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$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.