What is the generating function to the number of ways of expressing n dollars as a 1,2 and 5 dollar coins.

Question

I need to solve this problem using generating functions:

What is the generating function to the number of ways of expressing n dollars as a 1,2 and 5 dollar coins.

I wasn't able to solve the $\ (1+x^2+x^4)^n\ $ part.

Answer 1

We're looking for $$F(x) = \sum_{n=0}^\infty a_nx^n $$ where $a_n$ is the number of ways of expressing $n$ dollars as a collection of $1, 2, 5$ dollar coins. $$a_n = \sum_{k_1+k_2+k_3 = n} m_{k_1, 1}m_{k_2, 2}m_{k_3, 5} $$ where $m_{k_1, 1}$ is the number of ways to express $k_1$ dollars in terms of $1$ dollar coins, $m_{k_2, 2}$ is the number of ways of expressing $k_2$ dollars in terms of $2$ dollar coins, and $m_{k_3, 5}$ is the number of ways of expressing $k_3$ dollars in terms of $5$ dollar coins. From this: $$F(x) = \left(\sum_{n=0}^\infty m_{n, 1}x^n\right)\left(\sum_{n=0}^\infty m_{n, 2}x^n\right)\left(\sum_{n=0}^\infty m_{n, 5}x^n\right) = \left(\sum_{n=0}^\infty x^n\right)\left(\sum_{n=0}^\infty x^{2n}\right)\left(\sum_{n=0}^\infty x^{5n}\right)=\\ = \frac{1}{1-x}\cdot \frac{1}{1-x^2}\cdot \frac{1}{1-x^5} $$ If the order of the coins is important, then we can derive a recurrence: $$b_{n+5} = b_{n+4}+b_{n+3}+b_n,\ n\geq 0 \\ b_0 = 0,\ b_1 = 1,\ b_2 = 2, \ b_3 = 3, \ b_4 = 5$$ It's because there is $3$ possible cases, we have $1, 2$ or $5$ dollar coin at the end, and we take as much dollars from the whole if that's the case. Then we have $$G(x) = \sum\limits_{n=0}^\infty b_nx^n = x+2x^2+3x^3+5x^4+\sum\limits_{n=0}^\infty b_{n+5}x^{n+5} = \\ = p(x)+\sum_{n=0}^\infty (b_{n+4}+b_{n+3}+b_n)x^{n+5} = p(x)+\sum_{n=0}^\infty b_nx^{n+5} + \sum_{n=0}^\infty b_{n+3}x^{n+5} + \sum_{n=0}^\infty b_{n+4}x^{n+5} $$ where $p(x) = x+2x^2+3x^3+5x^4$. Then we can simplify the $3$ sums $$\sum_{n=0}^\infty b_nx^{n+5} = x^5\sum_{n=0}^\infty b_nx^n = x^5G(x) $$ $$\sum_{n=0}^\infty b_{n+3}x^{n+5} = x^2\sum_{n=0}^\infty b_{n+3}x^{n+3} = x^2\sum_{n=3}^\infty b_nx^n = x^2(\sum_{n=0}^\infty b_nx^n - \sum_{n=0}^2 b_nx^n)= \\ = x^2(G(x)-2x^2-x) = x^2G(x) - 2x^4-x^3 $$ $$\sum_{n=0}^\infty b_{n+4}x^{n+5} = x\sum_{n=0}^\infty b_{n+4}x^{n+4} = x\sum_{n=4}^\infty b_nx^n = x(\sum_{n=0}^\infty b_nx^n - \sum_{n=0}^3 b_nx^n) = \\ = x(G(x)-3x^3-2x^2-x) = xG(x)-3x^4-2x^3-x^2 $$ So we can now calulate what $G(x)$ is $$G(x) = p(x)+(x^5+x^2+x)G(x)-5x^4-3x^3-x^2 = (x^5+x^2+x)G(x)+x+x^2 $$ $$G(x) = \frac{x+x^2}{1-(x+x^2+x^5)} $$

Answer 2

The generating function for coins of value $k$ is $\dfrac1{1-x^k}$.

For different value coins, multiply their generating functions.