What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$?
So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is $30$. But obviously this number of numbers includes many overlaps (if for instance the requested sum was $8$, then $80=800=8000=134=143=431$ etc.). How do I get rid of the overlaps (inclusion-exclusion)?
Thanks in advance for any assistance!
One looks for the number $N$ of integer solutions of $$ \sum_{i=1}^6n_i=30,\qquad 0\leqslant n_i\leqslant9. $$ Thus, $N$ is the coefficient of $x^{30}$ in the polynomial $$ \prod_{i=1}^6\sum_{n_i=0}^9x^{n_i}=\left(\frac{1-x^{10}}{1-x}\right)^6. $$ To compute $N$, note that $$ (1-x^{10})^6=\color{red}{1}-\color{red}{6}x^{10}+\color{red}{15}x^{20}-\color{red}{20}x^{30}+o(30), $$ and that $$ \frac{1}{(1-x)^6}=\sum_{k=0}^{30}\color{green}{{5+k\choose5}}x^k+o(30), $$ where $o(30)$ denotes terms of order at least $31$, hence $$ N=\color{red}{1}\cdot\color{green}{{5+30\choose5}}-\color{red}{6}\cdot\color{green}{{5+20\choose5}}+\color{red}{15}\cdot\color{green}{{5+10\choose5}}-\color{red}{20}\cdot\color{green}{{5+0\choose5}}=50877. $$
The problem isn’t overlaps: it’s restricting the values to the range from $0$ through $9$. You’re looking for the number of solutions in non-negative integers to the equation
$$x_1+x_2+x_3+x_4+x_5+x_6=30\tag{1}$$
with the added requirement that $x_k\le 9$ for $k=1,\dots,6$: each of those solutions defines one of the numbers that you’re trying to count, and vice versa. The number of solutions without the upper bound restriction is, as you say,
$$\binom{30+6-1}{6-1}=\binom{35}5\;.$$
However, some of those solutions require ‘digits’ greater than $9$. Start by counting the solutions in non-negative integers to $(1)$ that have $x_1\ge 10$. Those are clearly in one-to-one correspondence with solutions in non-negative integers to
$$y_1+x_2+x_3+x_4+x_5+x_6=20\;,$$
where $y_1=x_1-10$, and you know how to compute their number. Call that number $n_1$. There are just as many solutions to $(1)$ that violate the upper bound on $x_2$, just as many again that violate the upper bound on $x_3$, and so on, so a better approximation to the solution to the original problem is
$$\binom{35}5-6n_1\;.$$
Of course this overcorrects, since it’s possible for a solution to $(1)$ to violate two of the upper bound constraints at once. You’ll have to calculate the number $n_2$ of solutions that have $x_1\ge 10$ and $x_2\ge 10$ and then add back the appropriate multiple of $n_2$. And since it’s actually possible to violate as many as three of the constraints at once, you’ll have to make one further inclusion-exclusion correction.
HINT: Can you find the number of integer soloutions of the equation $$x_1+x_2+x_3+x_4+x_5+x_6=30$$ such that $0\leq x_i\leq 9$ for all $i$. Use generating functions!
