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.
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.
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*}$