How many numbers are between $1$ and $9999$ in this case?
How many natural numbers between $1$ and $9999$ have the sum of the digits:
$a)$ equal to $9$.
$b)$ equal to $16$
My atempt: So for $a)$, I did $\dbinom {9+4-1} {4-1} = 220$ For $b)$, I calculated the total solution just like in the first case and I got $969$. Now, since the digits are between $0$ and $9$, I have to take away the number of solutions between $10-16$. Let's say that $x_1, x_2, x_3, x_4$ are the digits. So if one of them is $10$ then the sum of the remaining three is 6 and the number of solutions is: $\dbinom {4} {1} \cdot \dbinom {6+3-1} {3}$. I did the exact same thing for the cases where one of them is $11, 12, 13, 14, 15$ or $16$. I add them and got $336$. The final solution for me is: $969-336=633$.
Is it correct?
$\endgroup$ 22 Answers
$\begingroup$Your answer to the first question is correct. However, your answer to the second question is not. Let's see why.
How many natural numbers between $1$ and $9999$ have digit sum $16$?
By appending leading zeros to a number with fewer than four digits, we can express each positive integer less than $10,000$ as a four-digit string. For instance, the number $17$ is represented by $0017$. Thus, if we let $x_i$ represent the digit in the $i$th position, the number of positive integers less than $10,000$ that have digit sum $16$ is the number of solutions of the equation$$x_1 + x_2 + x_3 + x_4 = 16 \tag{1}$$in the nonnegative integers subject to the restrictions that $x_i \leq 9$ for $1 \leq i \leq 4$.
A particular solution of equation 1 corresponds to the placement of $4 - 1 = 3$ addition signs in a row of $16$ ones. For instance,$$1 1 1 + + 1 1 1 1 1 + 1 1 1 1 1 1 1 1$$corresponds to the solution $x_1 = 3$, $x_2 = 0$, $x_3 = 5$, $x_4 = 8$. The number of solutions of equation 1 in the nonnegative integers is the number of ways we can place three addition signs in a row of $16$ ones, which is $$\binom{16 + 4 - 1}{4 - 1} = \binom{19}{3}$$since we must choose which three of the $19$ positions required for $16$ ones and $3$ addition signs will be filled with addition signs.
From these, we must subtract those cases in which one or more of the $x_i$'s exceeds $9$. At most one $x_i$ can exceed $9$ since $2 \cdot 10 = 20 > 16$.
Suppose $x_1 > 9$. Then $x_1' = x_1 - 10$ is a nonnegative integer. Substituting $x_1' + 10$ for $x_1$ in equation 1 yields\begin{align*} x_1' + 10 + x_2 + x_3 + x_4 & = 16\\ x_1' + x_2 + x_3 + x_4 & = 6 \end{align*}which is an equation in the nonnegative integers with $$\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$$solutions.
By symmetry, there are an equal number of solutions in which $x_i > 9$ for each $i$ satisfying $1 \leq i \leq 4$. Hence, the number of solutions of equation 1 in which no $x_i$ exceeds $9$ is $$\binom{19}{3} - \binom{4}{1}\binom{9}{3}$$which is equal to the number of positive integers less than $10,000$ with digit sum $16$.
What error did you make?
You tried to subtract off the number of solutions in which one of the variables equals $10$. Suppose that variable is $x_4$. Then \begin{align*} x_1 + x_2 + x_3 + 10 & = 16\\ x_1 + x_2 + x_3 & = 6 \end{align*}which is an equation in the nonnegative integers with $$\binom{6 + 3 - 1}{3 - 1} = \binom{8}{2}$$ solutions. By symmetry, there are $$\binom{4}{1}\binom{8}{2}$$solutions in which a variable equals $10$.
By similar argument, there are$$\binom{4}{1}\binom{7}{2}$$solutions of equation 1 in which a variable equals $11$,$$\binom{4}{1}\binom{6}{2}$$solutions of equation 1 in which a variable equals $12$,$$\binom{4}{1}\binom{5}{2}$$solutions of equation 1 in which a variable equals $13$,$$\binom{4}{1}\binom{4}{2}$$solutions of equation 1 in which a variable equals $14$,$$\binom{4}{1}\binom{3}{2}$$solutions of equation 1 in which a variable equals $15$, and$$\binom{4}{1}\binom{2}{2}$$solutions of equation 1 in which a variable equals $16$.
Hence, the number of positive integers less than $10,000$ with digit sum $16$ is $$\binom{19}{3} - \binom{4}{1}\left[\binom{8}{2} + \binom{7}{2} + \binom{6}{2} + \binom{5}{2} + \binom{4}{2} + \binom{3}{2} + \binom{2}{2}\right]$$
$\endgroup$ $\begingroup$Stars and bars.
In the first case, you have 9 stars to allocate over 4 bins, or 9 stars and 3 bars.
${9+3\choose 3}$
In the second case you have 16 stars and 3 bars and you cannot but more than 9 stars in any one bin.
${19\choose3} - 4{10\choose 3}$
$\endgroup$
