Using generating functions, find 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?

  • $\begingroup$ Why do you have $1/(1-x)^2$? $\endgroup$ – Yuval Filmus Jun 29 '15 at 3:22
  • $\begingroup$ because of the dollar coins and $1 bills $\endgroup$ – Miriam Jun 29 '15 at 3:26
  • $\begingroup$ Perhaps you should emphasize that you want to find it by hand and not using a computer. $\endgroup$ – Yuval Filmus Jun 29 '15 at 4:09
  • $\begingroup$ If you're doing it by hand, partial fractions looks like the way to go. $\endgroup$ – Greg Martin Jun 29 '15 at 4:44

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, extracting $x^{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.

  • $\begingroup$ 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. $\endgroup$ – Greg Martin Jun 29 '15 at 4:43
  • $\begingroup$ 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. $\endgroup$ – Dr Xorile Jun 29 '15 at 4:52

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.