Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.