# Finding number of integer solutions using Generating Functions

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?

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

• Oh man. I've spent hours pouring over my homework for something that was trivial. I appreciate your help. – Nxt3 Feb 11 '15 at 4:59
• 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. – Thomas Andrews Feb 11 '15 at 5:00
• No kidding. My Data Structures class is nuts. We just got into Skip Lists--looks fun. :P – Nxt3 Feb 11 '15 at 5:12

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