1
$\begingroup$

Find the number of nonnegative integer solutions for the equation using generating functions $$y_{1}+2y_{2}+2y_{3}=n$$ I'm going to let $$y_{1}=e_{1}$$ $$2y_{2}=e_{2}$$ $$2y_{3}=e_{3}$$ so it becomes $$e_{1}+e_{2}+e_{3}=n$$

I can represent it as the product $$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^2+x^4+...)$$ $$=\frac{1}{1-x}\frac{1}{(1-x^2)}\frac{1}{(1-x^2)}$$ $$=\frac{1}{(1-x)^3(1+x)^2}$$

Then I could set up partial fractions to find the number of nonnegative integer solutions- is there a better way to do this? or can you help me complete this problem please?

$\endgroup$
2
$\begingroup$

You are almost there. Note that we have $$g(x) = \dfrac1{(1-x)^3(1+x)^2} = \dfrac{1+x}{(1-x^2)^3}$$ And we have $$(1-x^2)^{-3} = \sum_{k=0}^{\infty} \dbinom{k+2}{2}x^{2k}$$ Hence, $$(1+x)(1-x^2)^{-3} = \sum_{k=0}^{\infty} \dbinom{k+2}{2}\left(x^{2k} +x^{2k+1}\right) \tag{$\star$}$$ Now you should be able to get what you want.

Updated on OP's request:

Note that $(\star)$ can be written as $$\sum_{n=0} a_n x^n$$ where $$a_n = \begin{cases} \dbinom{n/2+2}2 & \text{if $n$ is even}\\ \dbinom{(n+1)/2 +1}2 & \text{if $n$ is odd}\end{cases}$$ and $a_n$ is the number you are after, i.e., $a_n$ gives the number of non-negative integer solutions to $y_1 + 2y_2 + 2y_3 = n$.

$\endgroup$
  • $\begingroup$ Can you please continue with your explanation? It's been very helpful but I don't know where to go from here. Thank you! $\endgroup$ – user2553807 Dec 4 '13 at 22:16

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.