Number of integer solutions by generating functions method

505 Views Asked by At

I'm stuck in the middle of a problem and not sure where to go next. The original problem is:

Find the number of integer solutions to the equation

$$2x + 3y + 4z + w + s + t = n$$ with $$0 \le w \le 2$$ $$2 \le s \le 5$$ $$0 \le t \le 3$$

Now I was able to create my generating functions equations to get my overall equation to this:

$$ G(x) = (\frac{1}{1-x^2})(\frac{1}{1-x^3}) (\frac{1}{1-x^4})(1+x+x^2)(x^2+x^3+x^4+x^5)(1+x+x^2+x^3) $$

Which with the help of the finite geometric series and some cancelling I was able to simplify down to:

$$ G(x) = (\frac{1}{1-x^2})(\frac{x^2}{1}) (\frac{1}{(1-x)^3})(\frac{1-x^4}{1}) $$

But now I'm stuck. Any help would be appreciated. Thanks.

Edit: With the extra step of simplification

$$ G(x) = (\frac{x^2}{1}) (\frac{1}{(1-x)^3})(\frac{1+x^2}{1}) $$

2

There are 2 best solutions below

2
On BEST ANSWER

Hint: you can factor $1-x^2$ and $1-x^4$.

0
On

You end up with: \begin{align} [x^n] G(x) &= [x^n] \frac{x^2 + x^4}{(1 - x)^3} \\ &= [x^{n - 2}] (1 - x)^{-3} + [x^{n - 4}] (1 - x)^{-3} \\ &= \binom{-3}{n - 2} (-1)^{n - 2} + \binom{-3}{n - 4} (-1)^{n - 4} \\ &= \binom{n - 2 + 3 - 1}{3 - 1} + \binom{n - 4 + 3 - 1}{3 - 1} \\ &= \frac{n (n - 1)}{2} + \frac{(n - 2) (n - 3)}{2} \\ &= n^2 - 3 n + 3 \end{align}