Discrete Math Counting Question

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?

-

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.

-
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