2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Feb 7 '18 at 12:44
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.