Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
show 4 more comments

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

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

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.