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.

I need help with one of those question where you have to count the number of ways you can place r objects into n distinct boxes kinds. I was wondering if someone could solve an example in detail.

How many positive integers greater than equal to 1 and less than or equal to 10010 have the property that the sum of their digits is exactly 9?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Split the count into two parts: the positive integers less than $10000$, which are all of the positive integers having at most four digits, and those between $10000$ and $10010$ inclusive. The latter part contains only one integer whose digits sum to $9$, namely, $10008$, so we need only add $1$ to whatever figure we get for the first part.

Think of the integers from $1$ through $9999$ as four-digit integers, padding with initial zeroes if necessary. Say that the digits are $d_1,d_2,d_3$, and $d_4$. Then you’re asking for the number of solutions in non-negative integers to the equation $d_1+d_2+d_3+d_4=9$. This is a standard stars-and-bars problem; the answer is $$\binom{9+4-1}{4-1}=\binom{12}3\;.$$ The reasoning behind that answer is explained fairly well at the link; try reading that, and I’ll try to answer any questions that you may then have.

share|improve this answer
    
Nice explanation, Brian. +1 if I were not out of votes! ;-) –  amWhy Apr 7 '13 at 22:54
    
@amWhy: Thanks. It evens out: I’m capped anyway. :-) –  Brian M. Scott Apr 7 '13 at 22:55
    
great answer :) so that means the total number of digits in this case would be 221 right? –  jack Apr 7 '13 at 23:07
    
@jack: Thanks. Yes, that’s what I get. –  Brian M. Scott Apr 7 '13 at 23:08

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.