11
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Namaste Nov 24 '16 at 16:21
10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

The answer will be 30492.

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

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Sorry !! Didn't get exactly . Can u please be more elaborative ? $\endgroup$ – Jon Garrick Nov 24 '16 at 15:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Nov 24 '16 at 16:40

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.