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 ?
Best Answer
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}$$