How many numbers from $1$ to $99999$ have the sum of the digits $= 15$?

Question

The problem:

How many numbers from $1$ to $99999$ have the sum of the digits $= 15$?

I thought of using the bitstring method and $x_1 + x_2 + x_3 + x_4 + x_5$ will be the boxes therefor we have $4$ zeros and $15$ balls. I'd say the answer would have to be $\binom{19}{15}$ is it right?

Answer 1

First you have to compute the different ways to obtain 15 by a sum of at most 5 digits ($\neq 0$). Then, for each solution, let denote by $n$ the number of digits of the solution ($n<5$), $r$ the numbers of the strictly different digits ($r\leq n$) and $n_1$, ..., $n_r$ the number of each different digit ($n_1+\cdots+n_r=n$) : you will have then $\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots \underbrace{\binom{n-(n_1+\cdots+n_{r-1})}{n_r}}_{=1}\binom{5}{n}$ solutions associated with this decomposition.

Remark: if $n=r$, then $n_1=\cdots=n_r=1$ and $\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots \binom{n-(n_1+\cdots+n_{r-1})}{n_r}=n!$

For example : decomposition with

1 digits :0

2 digits : 2 (9+6=8+7)

That will give $2\binom{5}{2}+ 2\binom{5}{2}=40$ such numbers

3 digits :
\begin{align*} &9+(5+1) = 9+(4+2)=9+(3+3) \\ &8+(6+1) = 8+(5+2)=8+(4+3) \\ &7+(6+2) = 7+(5+3)=7+(4+4) \\ &6+(5+4) \\ & 5+5+5 \end{align*}

That will give $9\times 3!\binom{5}{3}+ \binom{3}{1}\binom{5}{3}+ \binom{5}{3}=580$

4 digits : \begin{align*} &9+(4+1+1) = 9+(3+2+1)=9+(2+2+2) \\ &8+(5+1+1) = 8+(4+2+1)=8+(3+3+1)=8+(3+2+2) \\ &7+(6+1+1) = 7+(5+2+1)=7+(4+3+1)=7+(4+2+2)=7+(3+3+2) \\ &6+(5+3+1)=6+(5+2+2)=6+(4+3+2)=6+(3+3+3)\\ & 5+5+4+1 =5+5+3+2=5+4+3+3 \end{align*} $6\times 4!\binom{5}{4}+ 11\times \binom{4}{2}\binom{2}{1}\binom{5}{3}+ 2\times \binom{4}{3}\binom{5}{3}=2120$

5 digits : \begin{align*} &9+(3+1+1+1) = 9+(2+2+1+1) \\ &8+(4+1+1+1) = 8+(3+2+1+1)=8+(2+2+2+1) \\ &7+(5+1+1+1) = 7+(4+2+1+1)=7+(3+3+1+1)=7+(3+2+2+1)=7+(2+2+2+2) \\ &6+(5+2+1+1)=6+(4+3+1+1)=6+(4+2+2+1)=6+(3+3+2+1)=6+(3+2+2+2)\\ & 5+5+3+1+1 =5+5+2+2+1=5+4+3+2+1= 5+4+2+2+2= 5+3+3+2+2 \\ & 4+4+4+2+1=4+4+3+3+1=4+4+3+2+2=4+3+3+3+2 \\ & 3+3+3+3+3 \end{align*} ($r=5$ : 1 occurence ; $r=4$ : 7 occurence ; $r=3$ : 15 occurence ; $r=2$ : 1 occurence ; $r=1$ : 1 occurence)

Verification with Python code:

def sum_digits(n):
        s = 0
        while n:
            s += n % 10
            n //= 10
        return s

A=[x for x in range(1,99999) if sum_digits(x)==15]

In [7]: len(A)
Out[7]: 3246

Answer 2

Your answer is incorrect since you have not considered the restriction that a digit in the decimal system cannot exceed $9$.

We want to find the number of positive integers between $1$ and $99~999$ inclusive that have digit sum $15$. Since $0$ does not have digit sum $15$, we get the same answer by considering nonnegative numbers less than or equal to $99~999$ with digit sum $15$.

A nonnegative number with fewer than five digits such as $437$ can be viewed as a string of five digits by appending leading zeros. In this case, $437$ can be represented as the string $00437$. Hence, we can view the problem as finding the number of five-digit decimal strings with digit sum $15$. Hence, we seek the number of solutions in the nonnegative integers of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 15 \tag{1}$$ subject to the restrictions that $x_j \leq 9$ for $1 \leq j \leq 5$.

As you determined, the number of solutions of equation 1 is $$\binom{15 + 5 - 1}{5 - 1} = \binom{19}{4} = \binom{19}{15}$$ From these, we must subtract those solutions in which one or more of the variables exceeds $9$. Since $2 \cdot 10 = 20 > 15$, at most one of the variables can exceed $9$.

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 + x_5 & = 15\\ x_1' + x_2 + x_3 + x_4 + x_5 & = 5 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{5 + 5 - 1}{5 - 1} = \binom{9}{4}$$ solution. By symmetry, there are $\binom{9}{4}$ solutions that violate the restrictions for each of the five variables that could exceed $9$. Hence, the number of positive integers less than or equal to $99~999$ with digit sum $15$ is $$\binom{19}{4} - \binom{5}{1}\binom{9}{4}$$