# How many positive integers less than 1,000,000 have the sum of their digits equal to 19?

How many positive integers less than $1,000,000$ have the sum of their digits equal to $19$ ?

I tried to answer it by using stars and bars combinatorics method.

The question says that sum of $6$ digit numbers { considering the number as $abcdef$ } is 19.

Hence, I can write it as $a + b + c + d + e + f = 19$ ,but this assumes that $a,b,c,d,e,f >= 0$ .

But, here each digit lies between 0 and 9. So, how stars and bars method will be modified according to this domain ?

• You'll need for three or more of the digits $a, b, c, d, e, f$ to be nonzero (since no two of the digits in $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\})$ sum to $19$. Stars and Bars (two forms) does not take into account – Namaste Nov 24 '16 at 16:21

If we treat each positive integer with fewer than six digits as a six-digit string with leading zeros, we seek the number of solutions of the equation $$a + b + c + d + e + f = 19 \tag{1}$$ in the non-negative integers subject to the restrictions that $a, b, c, d, e, f \leq 9$. A particular solution of equation 1 corresponds to the placement of five addition signs in a row of $19$ ones. For instance, $$1 1 1 + 1 1 + 1 1 1 1 + 1 1 1 1 1 1 + + 1 1 1 1$$ corresponds to the solution $a = 3$, $b = 2$, $c = 4$, $d = 6$, $e = 0$, and $f = 4$. Hence, if there were no such restrictions, the number of solutions would be equal to the number of ways we can insert five addition signs into a row of $19$ ones, which is $$\binom{19 + 5}{5} = \binom{24}{5}$$ since we must choose which five of the $24$ symbols (five addition signs and nineteen ones) are addition signs.

However, we have counted solutions in which one or more of the variables exceeds $9$. There can only be one such variable since $2 \cdot 10 = 20 > 19$. We must exclude solutions in which one of the variables exceeds $9$.

We count the number of solutions in which $a > 9$. Since $a$ is an integer, then $a \geq 10$. Hence, $a' = a - 10$ is a non-negative integer. Substituting $a' + 10$ for $a$ in equation 1 yields \begin{align*} a + b + c + d + e + f & = 19\\ a' + 10 + b + c + d + e + f & = 19\\ a' + b + c + d + e + f & = 9 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers. Consequently, the number of solutions of equation 1 in which $a > 9$ is $$\binom{9 + 5}{5} = \binom{14}{5}$$ By symmetry, there are $$\binom{14}{5}$$ solutions for each of the six variables that could exceed $9$. Hence, the number of positive integers less than $1,000,000$ with digit sum $19$ is $$\binom{24}{5} - \binom{6}{1}\binom{14}{5}$$

Note - 1,000,000 has sum of digit = 1.

Then we are concerned with numbers between 1 - 999,999.

Let us assign an alphabet for every digit.

u+v+w+x+y+z=19 has 24C5= 42504

if u=10 then v+w+x+y+z =9 has 13C4 = 715

if u=11 then v+w+x+y+z =8 has 12C4 =495

if u=12 then v+w+x+y+z =7 has 11C4=330

if u=13 then v+w+x+y+z =6 has 10C4=210

if u=14 then v+w+x+y+z =5 has 9C4=126

if u=15 then v+w+x+y+z =4 has 8C4=70

if u=16 then v+w+x+y+z =3 has 7C4=35

if u=17 then v+w+x+y+z =2 has 6C4=15

if u=18 then v+w+x+y+z=1 has 5C4=5

if u=19 then v+w+x+y+z=0 has 4C4=1

The total is = 2002 for u>10

Now, any one u, v, w, x, y, z can be more than 10.

Hence, 2002 x 6 = 12012

So, answer = 42504 - 12012 = 30492

• This answer is seriously unclear and looks false to me. – Chris Jan 26 '17 at 13:41
• The answer is correct numerically and methodically; only the writeup leaves something to be desired. – Christian Blatter Jan 26 '17 at 14:07
• @chris where i was wrong? – Dhavalkumar Prajapati Feb 2 '17 at 17:42

The number is $<$ $1000000$ ,

$\Rightarrow$ it contains 6 digits. Each of these digits can be one of $0,1,2,3....9$

$\Rightarrow$ problem reduces to no of integral solution to the following equation

$d_1+d_2+d_3+d_4+d_5+d_6 = 19$ where $0\leq d_i \leq 9$

Using generating function :

\begin{align*} & \ \ \ \left [ x^{19} \right ]\left ( 1+x+x^2+x^3+....+x^9 \right )^{6} \\ &=\left [ x^{19} \right ]\left [ \frac{1-x^{10}}{1-x} \right ]^{6}\\ &=\left [ x^{19} \right ]\left ( 1-x^{10} \right )^{6}. \sum_{r=0}^{\infty}\binom{5+r}{r}.x^{r} \\ &=\left [ x^{19} \right ]\left [ \sum_{r=0}^{6}.\binom{6}{r}.\left ( -x^{10} \right )^{r} \right ]. \left [ \sum_{r=0}^{\infty}\binom{5+r}{r}.x^{r} \right ] \\ &=\left ( -1 \right )^{0}*\binom{24}{19} + \left ( -1 \right )^{1}*6*\binom{14}{9} \\ &=30492\\ \end{align*}

NOTE:

1. $1+x+x^2+x^3+.....x^n = \frac{1-x^{n+1}}{1-x}$

2. $\frac{1}{(1-x)^n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}.x^r$

3. $\left [ x^{19} \right ]$ means coefficient of $x^{19}$ of the whole expression.

Add one to each of $a,b,c,d,e,f$ and make the sum $25$. All the new variables have to be positive. You still have to worry about the fact that none of the new variables can exceed $10$

• Sorry !! Didn't get exactly . Can u please be more elaborative ? – Jon Garrick Nov 24 '16 at 15:20
• Define new variables $a'=a+1$ etc. Then $a'$ can range from $1$ to $10$, so none of the new variables can be zero. That makes stars and bars work. The sum has to be increased to account for the $+1$s. Unfortunately basic stars and bars will count cases where some of the variables are greater than $10$, so you need to subtract those off. – Ross Millikan Nov 24 '16 at 16:40