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

Using generating functions, ﬁnd 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.

• Do you mean you're in an exam and now want random strangers on the internet to help you cheat? Commented Oct 10, 2012 at 9:23
• I mean, I have an exam in 4 hours. Commented Oct 10, 2012 at 9:24
• The title is ambiguous. Interpreted literally, it says that this question is part of an exam, which means that people are unlikely to want to help. If you mean something else, you’ll need to make that clear. Commented Oct 10, 2012 at 9:24
• I am sorry, I have an exam at 10 am in Eastern Time. I need help before exam. Thank you. Commented Oct 10, 2012 at 9:24
• This problem is discussed in deetails in the relevant section of Concrete Mathematics
– Alex
Commented Oct 10, 2012 at 9:33

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

• Thank you very much. I wanted to know how do you add constraints on like at most 2 dollar bills or at least one 5 dollar bill? Commented Oct 10, 2012 at 9:45
• @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.
– wj32
Commented Oct 10, 2012 at 9:52