How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$?

Solution 1:

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.

Solution 2:

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}$$

Solution 3:

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$

How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$?

Solution 1:

Solution 2:

Solution 3:

Related

Recent Posts