# Find the number of integer solutons to $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60$.

Find the number of integer solutons to $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60$ if $x_1 \geq2, x_2\geq 5, 2\leq x_3\leq 7, x_4\geq 1, x_5\geq 3, x_6\geq 2$.

Here is my approach: If you let $M = \{\infty x_1, \infty x_2, \infty x_3, \infty x_4, \infty x_5, \infty x_6\}$, then a multisubset of $M$ of size $60$ will represent such a solution, for example $\{20x_1, 15x_2, 15x_3, 10x_4, 0x_5, 0x_6\}$. It can generally be proven that there are ${n+r-1\choose r}$ multisubsets of size $r$ of a multiset with $n$ types. Since we know that $x_1\geq 2, x_2\geq 5...$, we need to count the multisubsets of size $60 - (2+5+2+1+3+2) = 45$,but there musnt be greater than 7 $x_3$'s, so we split it into cases. Case 1: $2$ $x_3$'s ,so there are $49\choose45$ such solutions . Case 2: $3$ $x_3$'s so $48\choose 45$ such solutions and so on to get a total of ${49\choose 45} + {48\choose 44} + {47\choose 43} + {46\choose 42} + {45\choose 41} = 897001$ solutions. But the answer in the book is $1032752$, so there must be some mistake. The question is where is that mistake?

• related Jun 14 '15 at 12:19
• I just did a quick MATLAB program to check this, and the $1032752$ number is correct. Jun 14 '15 at 12:26

Your mistake is not doing all six cases; you need to add $44\choose40$ to the count.

$$S(x)=\underbrace{(x^2+x^3+\cdots)}_{x_1}\underbrace{(x^5+x^6+\cdots)}_{x_2}\underbrace{(x^2+x^3+\cdots+x^7)}_{x_3}\underbrace{(x+x^2+\cdots)}_{x_4}\\\times\underbrace{(x^3+x^4+\cdots)}_{x_5}\underbrace{{(x^2+x^3+\cdots)}}_{x_6}\\ ={x^2\over1-x}{x^5\over1-x}{x^2(1-x^6)\over 1-x}{x\over1-x}{x^3\over1-x}{x^2\over1-x}={x^{15}(1-x^6)\over(1-x)^6}\\ (1-x)^{-6}=\sum_{r=0}^{\infty}{6\cdot7\cdots(6+r-1)\over r!}x^r$$

Every solution of the equation contributes $1$ to the coefficient of $x^{60}=x^{x_1+x_2+\cdots x_6}$ in $S(x)$. For example if we take $x_1=2,x_2=5,x_3=2,x_4=4,x_5=3,x_6=44$, we can pick $x^2,x^5,x^2,x^4,x^3,x^{44}$ from the $1$-st, $2$-nd,...and $6$-th term respectively to construct $x^{60}$.

Coefficient of $x^{60}$ in $S(x)$ is $${{6\cdot7\cdots(6+45-1)\over 45!}}-{{6\cdot7\cdots(6+39-1)\over 39!}}=1032752$$

• I am sorry, I dont understand what you have written and how this solves the problem. Jun 14 '15 at 13:11
• He is using generating functions
– user242594
Jun 14 '15 at 13:38

Another method would be to substitute

$y_1=x_1-1, y_2=x_2-5, y_3=x_3-2, y_4=x_4-1, y_5=x_5-3, y_6=x_6-2$;

this gives the equivalent equation $y_1+\cdots+y_6=45$ where $y_i\ge0$ for each $i$ and $y_3\le5$.

Since the number of integer solutions without the last restriction is given by $\dbinom{50}{5}$,

and the number of solutions with $y_3\ge6$ is given by $\dbinom{44}{5}$, the answer is $\dbinom{50}{5}-\dbinom{44}{5}$.