# Generating functions of bills

Using generating functions, ﬁnd the number of ways to make change for a $\$$100 bill using only dollar coins and \$$1,$\$$5, and \$$10 bills.

My answer: I had $1/(1-x)^2*(1-x^5)*(1-x^{10})=1/(1-x)^2*(1-x^5)^2*(1+x^5)$. I know I need to find the coefficient of $x^{100}$. What should I do next? My guess is partial fractions but the computation looks very long. So is there an easier way to determine the coefficient?

• Why do you have $1/(1-x)^2$? – Yuval Filmus Jun 29 '15 at 3:22
• because of the dollar coins and $1 bills – Miriam Jun 29 '15 at 3:26 • Perhaps you should emphasize that you want to find it by hand and not using a computer. – Yuval Filmus Jun 29 '15 at 4:09 • If you're doing it by hand, partial fractions looks like the way to go. – Greg Martin Jun 29 '15 at 4:44 ## 2 Answers Rewrite the generating function$G(x)as \begin{align*} G(x) &= \frac{1}{\left(1-x\right)^2\left(1-x^5\right)\left(1-x^{10}\right)}\\ &= \frac{\left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3}{\left(1-x^{10}\right)^4}\\ &= \left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3\sum_k \binom{k+3}{3} x^{10\, k} \end{align*} Now, extractingx^{10k}$gives $$[x^{10k}]G(x) = \binom{k+3}{3} + 15 \binom{k+2}{3}+4 \binom{k+1}{3}$$ For$k=10$, we get $$[x^{100}]G(x) = \binom{13}{3} + 15 \binom{12}{3}+4 \binom{11}{3} = 4246$$ So the generating function expansion can be truncated to:$ (1+x+x^2+\cdots +x^{100})^2. (1+x^5+x^{10}+\cdots +x^{100}). (1+x^{10}+x^{20}+\cdots + x^{100})$You're then looking for the coefficient of$x^{100}$. The first two terms (for the 1 dollar coins and the 1 dollar bills) become$1+2x+3x^2+\cdots +101x^{100}$plus higher powers. Only the powers that are multiples of 5 are now relevant. So you need only consider:$1+6x^5+11x^{10}+\cdots+101x^{100}$. This can be multiplied by the next term, and in a similar way, discard all powers that are odd multiples of 5:$1+18x^{10}+(1+6+11+16+21)x^{20}+...\$

Repeat for the final multiplication.

• This doesn't take into account the fact that there are both dollar bills and dollar coins. Even if it did, it doesn't mean that the OP's method is wrong: you are using polynomials that are truncations of the power series the OP is using. – Greg Martin Jun 29 '15 at 4:43
• Oh, I see what you mean. Okay, so you need the full expansion, because you can have a mixture of types of 1s. I'll adjust the answer. – Dr Xorile Jun 29 '15 at 4:52