1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Presumably $x,y,z$ are nonnegative integers? $\endgroup$ – Robert Israel Apr 21 '14 at 1:38
  • $\begingroup$ Yes they all are $\endgroup$ – KwakKwak Apr 21 '14 at 1:51
  • $\begingroup$ It would be better not to reuse $x$ between the equation and your generating function. Also if you use \left( and \right) in your $\LaTeX$ the parentheses expand to be large enough to enclose everything inside. $\endgroup$ – Ross Millikan Apr 21 '14 at 2:02
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I tried that but it only took me to an equally stuck situation so I just went back a step $\endgroup$ – KwakKwak Apr 21 '14 at 1:47
  • $\begingroup$ ... and then use partial fractions. $\endgroup$ – Robert Israel Apr 21 '14 at 2:09
2
$\begingroup$

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}

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