5
$\begingroup$

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?

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

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

$\endgroup$
4
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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