How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$? How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$?
Can someone tell me if I got the right answers? I solved both cases and I've got $148$ for $8$ and $633$ for $16$. I solved this problem using $x_1+x_2+x_3+x_4=8$ then $16$. After that I decided to take the case when $1$ number is bigger than $10$, but I'm not sure if that's the way I should do it for $8$. And then I substract the $4$ cases when $x_1=0$ and $7$ cases when $x_1=9$. Thank you.
 A: You're half-correct. By stars and bars, the number of solutions to $$x_1+x_2+x_3+x_4=8$$ is exactly $\binom{8+4-1}{4-1}=165$. I don't understand however why numbers like $8=0008$ don't count, since, as Thomas Andrews pointed out in the comments, the sum of its digits add up to $8$.

However, for $16$, our approach cannot be exactly the same, since a solution to $x_1+x_2+x_3+x_4=16$ could be $(x_1,x_2,x_3,x_4)=(1,2,3,10)$, but $10$ cannot be a digit, as those are always between $0$ and $9$. Since only one can be $10$ or larger, we can simply count the number of solutions where one is $10,11,\cdots,16$. If one is $10$, then we count the number of solutions to $x_1+x_2+x_3=16-10=6$. Use stars and bars again and we get $\binom{6+3-1}{3-1}$. Now we multiply by $4$ since we now chose $x_4=10$ but we also need to count $x_1,x_2,x_3=10$. So we get $4\binom{6+3-1}{3-1}$. Using this principle we get $$4\left(\binom{6+3-1}{3-1}+\binom{5+3-1}{3-1}+\cdots+\binom{0+3-1}{3-1}\right)=4\cdot84=336$$ The total amount of solutions to $x_1+x_2+x_3+x_4=16$, including those we don't want, are (again, stars and bars) $\binom{16+4-1}{4-1}=969$. Now substract the amount of solutions we don't want, and we get $969-336=633$ possibilities.
A: *

*This is a known problem healed by stars and bars theorem.


$C_8=\binom{8+3}{3}=165$


*

*For this case stars and bars theorem must be restricted to numbers <10, so we omit the case of one digit atleast exceeds 9, then we multiply by 4 regarding any digit.


therefore stars figure as follows:
********** ******|||

********** ****|**||

********** |*|**|***

...

so we omit $\binom{6+3}{3}$ cases
$C_{16}=\binom{16+3}{3}-4*\binom{6+3}{3}=633$
A: We treat a number with fewer than four digits as a number with leading zeros.  For instance, we regard the number $235$ as $0235$ and the number $8$ as $0008$.  Then the number of positive integers between $1$ and $9999$ with digit sum $8$ is equal to the number of solutions of the equation
$$x_1 + x_2 + x_3 + x_4 = 8 \tag{1}$$
in the non-negative integers.  A particular solution corresponds to the placement of three addition signs in a row of eight ones.  For instance, 
$$+ + + 1 1 1 1 1 1 1 1$$
corresponds to the choice $x_1 = x_2 = x_3 = 0$ and $x_4 = 8$.  Thus, the number of positive integers with up to four digits that have digit sum $8$ is 
$$\binom{8 + 3}{3} = \binom{11}{3}$$
since we must choose which three of the eleven symbols (eight ones and three addition signs) will be addition signs.
The number of positive integers between $1$ and $9999$ which have digit sum $16$ is the number of solutions of the equation
$$x_1 + x_2 + x_3 + x_4 = 16 \tag{2}$$
in the non-negative integers subject to the restrictions that $x_k \leq 9$ for $1 \leq k \leq 4$.  The number of solutions of equation 2 in the non-negative integers is 
$$\binom{16 + 3}{3}$$
From these, we must exclude those solutions in which at least one of the variables exceeds $9$.  Notice that since $2 \cdot 10 = 20 > 16$, at most one of the variables may exceed $9$.
Suppose $x_1 > 9$.  Let $y_1 = x_1 - 10$.  Then $y_1$ is a non-negative integer.  Substituting $y_1 + 10$ for $x_1$ in equation 2 yields
\begin{align*}
y_1 + 10 + x_2 + x_3 + x_4 & = 16\\
y_1 + x_2 + x_3 + x_4 & = 6 \tag{3}
\end{align*}
Equation $3$ is an equation in the non-negative integers with 
$$\binom{6 + 3}{3} = \binom{9}{3}$$
solutions.  By symmetry, there are $\binom{9}{3}$ solutions of equation 2 in which $x_k$ exceeds $9$ for $1 \leq k \leq 4$.  Hence, the number of solutions of equation 2 in which one of the variables exceeds $9$ is 
$$\binom{4}{1}\binom{9}{3}$$
Hence, the number of positive integers between $1$ and $9999$ which have digit sum $16$ is 
$$\binom{19}{3} - \binom{4}{1}\binom{9}{3}$$
