# Generating Functions help

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? – Henning Makholm Oct 10 '12 at 9:23
I mean, I have an exam in 4 hours. – snihalani Oct 10 '12 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. – Brian M. Scott Oct 10 '12 at 9:24
I am sorry, I have an exam at 10 am in Eastern Time. I need help before exam. Thank you. – snihalani Oct 10 '12 at 9:24
This problem is discussed in deetails in the relevant section of Concrete Mathematics – Alex Oct 10 '12 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? – snihalani Oct 10 '12 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 Oct 10 '12 at 9:52