W/ generating functions, How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$?

125 Views Asked by At

The question is: How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$? Solve this by writing down the correct generating function.

I have no idea how to go about this. Any help would be appreciated. I was also confused about the more basic problem: How many solutions are there to the equation $a+b+c+d=n$ for some integer $n \geq 0$ and $a, b, c, d \geq 0$? So possibly helping me with the more basic one would help me get to the main problem. Thank you!

1

There are 1 best solutions below

0
On

For the more basic question, think about the formal power series $$ f = (1+x+x^2+\cdots)^4. $$ When expanding this, what is the coefficient of $x^n$? To get a term of degree $n$, we need to choose terms of degrees $a,b,c,d$ such that $a+b+c+d=n$. For each of those choices we add $1$ to the coefficient of $x^n$, since the coefficients in $(1+x+x^2+\cdots)$ are all $1$. Hence, the coefficient of $x^n$ in the expansion of the above formal power series is equal to the number of solutions to $a+b+c+d=n$ for an integer $n\ge 0$ with non-negative integers $a,b,c,d$.

Now as formal power series $(1+x+x^2+\cdots)$ is the inverse of $(1-x)$, hence $$ f = \left(\frac{1}{1-x}\right)^4 = \frac{1}{(1-x)^4}. $$ You now have to find the coefficients in the taylor series of $1/(1-x)^4$ at $x=0$, can you do that?