Nonnegative Integer Solutions using Generating Functions

1.8k Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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