# Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$

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!

-
Just a note: If each digit would be random from $\{0, \ldots, 9\}$ then the sum of $6$ digits would approximately be distributed as $\mathcal{N}(27, 99/2)$ leading to about $\approx 51,750$ out of every $1,000,000$ numbers with sum $30$. This is pretty close to the actual number. –  TMM May 11 '13 at 18:29
(The lazy Mathematica-answer is $50,877$.) –  TMM May 11 '13 at 19:53

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.

-
Hi, thank you for the insight. I didn't think of the upper boundry! Now, as for you corrections. Would $n_1={20\choose 5}$? Also, I didn't understand your last paragraph. How can two of the upper bound constraints be violated at once? Or in short, I didn't understand the last paragraph idea :/ –  ohad May 11 '13 at 17:53
@ohad: Calculating $n_1$ is a stars-and-bars problem: $n_1=\binom{20+6-1}{6-1}=\binom{25}5$. The solution $x_1=x_2=15$, $x_3=x_4=x_5=x_6=0$ violates the upper bound constraints on both $x_1$ and $x_2$. The $6$-‘digit’ number $(11)23(12)11$ violates the constraints on $x_1$ and $x_4$. –  Brian M. Scott May 11 '13 at 18:03
Yes, my mistake. I understand now why there can be two and even three violations on that constraint, but how does that reflect on the number of numbers? Thanks and sorry to bother you so much. –  ohad May 11 '13 at 18:15
@ohad: It means that when we subtract $6\binom{25}5$ to get rid of the solutions that exceed one of the bounds, each solution that exceeds two bounds get subtracted twice and therefore counted $-1$ times in the total $\binom{35}5-6\binom{25}5$. We want to count it $0$ times, so we have to add it back in. There are $\binom{15}5$ solutions to $(1)$ that exceed the bounds on $x_1$ and $x_2$ (why?), and there are $\binom62$ pairs of variables, so there are $\binom62\binom{15}5$ solutions to $(1)$ that violate at least two constraints and have to be added back in. But if you check, ... –  Brian M. Scott May 11 '13 at 18:19
... you’ll find that every solution that violates three constraints (and there are some) has been counted once in $\binom{35}5$, $3$ times in $6\binom{25}5$, and $3$ times in $\binom62\binom{15}5$ (why?), for a total of $1-3+3=1$ time. But we don’t want to count those solutions, so we need to subtract them from $\binom{35}5-6\binom{25}5+\binom62\binom{15}5$. And that’s the last such correction that’s needed, since it’s impossible to get a total of $30$ with $4$ or more variables violating the constraint. –  Brian M. Scott May 11 '13 at 18:21

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

-
If I remember correctly, this is the first exercise in Polya-Szego's treatise. –  Did May 11 '13 at 19:43

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!

-