# 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

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

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: 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$. May 11 '13 at 18:03
• @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, ... 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. May 11 '13 at 18:21
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!