1
$\begingroup$

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

Thanks for the help.

  • 0
    This problem is discussed in deetails in the relevant section of Concrete Mathematics2012-10-10

1 Answers 1

4

Your generating function will have the form $f(x)=\sum_{n\ge 0}a_nx^n\;,$ where $a_n$ is the number of ways to make a total of $n$ dollars using the prescribed coin and bills. Each $\$1$ coin must therefore add $1$ to the exponent, as must each $\$1$ bill; each $\$2$ bill must add $2$ to the exponent, and each $\$5$ bill must add $5$. Thus,

$f(x)=\underbrace{(1+x+x^2+\ldots)}_{\$1\text{ coins}}\underbrace{(1+x+x^2+\ldots)}_{\$1\text{ bills}}\underbrace{(1+x^2+x^4+\ldots)}_{\$2\text{ bills}}\underbrace{(1+x^5+x^{10}+\ldots)}_{\$5\text{ bills}}\;,$

or more compactly,

$f(x)=\left(\sum_{n\ge 0}x^n\right)^2\left(\sum_{n\ge 0}x^{2n}\right)\left(\sum_{n\ge 0}x^{5n}\right)\;.$

Now use the basic geometric generating function to rewrite this as

$f(x)=\left(\frac1{1-x}\right)^2\left(\frac1{1-x^2}\right)\left(\frac1{1-x^5}\right)=\frac1{(1-x)^2(1-x^2)(1-x^5)}\;,$

which can be further simplified to $f(x)=\frac1{(1-x)^3(1+x)(1-x^5)}\;,$ if you wish.

The answer to the question is now the coefficient of $x^{100}$ in $f(x)$.

Added: Suppose that you want the number of $\$5$ bills to be at least $2$ and at most $6$. Then the factor that accounts for the $\$5$ bills would be

$\begin{align*} x^{2\cdot5}+x^{3\cdot5}+x^{4\cdot5}+x^{5\cdot5}+x^{6\cdot5}&=x^{10}+x^{15}+x^{20}+x^{25}+x^{30}\\ &=x^{10}\left(1+x^5+x^{10}+x^{15}+x^{20}\right)\\ &=\frac{x^{10}\left(1-x^{25}\right)}{1-x^5}\;. \end{align*}$

  • 0
    @snihalani: At least is easy - you just start from $x$ or $x^2$ instead of $1$. If you want at most $k$ things, then use $1+x+\cdots+x^k$. However, this can get tricky to compute.2012-10-10