3
$\begingroup$

This is a problem for a practice test my professor gave me.

$$\text{How many integer solutions are there to } x_1+x_2+x_3+x_4 \leq 50 \\ \text{with } x_i \geq 2 \text{ for all } i = 1,2,3,4 \text{ and } x_1,x_2 \leq 7 \text{?}$$


This is how I approached the problem, using generating functions:

$\text{Same as}$ $$x_1+x_2+x_3+x_4+x_5 = 50, \space x_5 \geq 0 $$ $\text{Find the coefficient of } x^{50} \text{ in}$ $$(x^2 + x^3 + x^4 + \dotso)^2 (x^2 + x^3 + x^4 + \dotso + x^7)^2 (1 + x + x^2 + x^3 + \dotso)$$

After some factoring, we'll have:

$$x^8(1+x^2+x^3+ \dotso + x^5)^2 (1+x+x^2+\dotso)^3$$

This is the same as:

$\text{Find the coefficient of } x^{42} \text{ in}$ $$(1+x^2+x^3+ \dotso + x^5)^2 (1+x+x^2+\dotso)^3$$

To simplify further:

$$(1-x^6)^2 \frac{1}{(1-x)^3}$$

So, this is where I'm confused. I was using the formula which is based off this answer on Math.SE, but I don't get the correct answer. According to my professor, the correct answer is:

$$\dbinom{30+5-1}{30} - 2\dbinom{36+5-1}{36} + \dbinom{42+5-1}{42} = 26,781$$


What I end up doing mirrors that of the linked question on Math.SE:

$$(1-x^6)^2 = 1-2x^6+x^{12} \\ \\ (1-2x^6+x^{12}) \frac{1}{(1-x)^3}$$ Using the formula from the linked question:

$\text{We do this three times, for } k=0, k=6, \text{ and } k=12$. The result is $$(1-2x^6+x^{12})\frac{1}{(1-x)^3}={m-0+2 \choose 2}- 2{m-6+2 \choose 2} + {m-12+2 \choose 2} \\ \ \\m = 42 \\ \ \\={42-0+2 \choose 2}- 2{42-6+2 \choose 2} + {42-12+2 \choose 2} = 36$$

As you can see, my answer differs greatly from what my professor said was correct. I don't understand why this formula I used doesn't work; I've used it for lots of other problems of this same type, and I calculated the correct number; for this one though, it doesn't seem to be working.

What am I doing wrong?

$\endgroup$
2
$\begingroup$

The actual generating function should be $$\frac{(1-x^6)^2}{(1-x)^5}$$ When you said, "To further simplify...," you forgot that $$1+x+x^2+x^3+x^4+x^5=\frac{1-x^6}{1-x},$$ not simply $1-x^6$.

$\endgroup$
  • $\begingroup$ Oh man. I've spent hours pouring over my homework for something that was trivial. I appreciate your help. $\endgroup$ – Nxt3 Feb 11 '15 at 4:59
  • $\begingroup$ it happens. I'm a computer programmer, and we spend hours looking for why stuff isn't working, and it often requires a second pair of eyes after a while. $\endgroup$ – Thomas Andrews Feb 11 '15 at 5:00
  • $\begingroup$ No kidding. My Data Structures class is nuts. We just got into Skip Lists--looks fun. :P $\endgroup$ – Nxt3 Feb 11 '15 at 5:12
2
$\begingroup$

Inclusion exclusion is easier than generating functions in this case. First you reduce to

$$ x_1 + x_2 + x_3 + x_4 + x_5 = 42 $$

where $x_i \geq 0$ and $x_1, x_2 \leq 5$. Then IE immediately gives

$$ {42+5-1 \choose 5-1} - 2{36+5-1 \choose 5-1} + {30+5-1 \choose 5-1} \\ = {46 \choose 4} - 2{40 \choose 4} + {34 \choose 4} = 26781 $$

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