# Change combinatorix

• Aug 28th 2007, 08:21 AM
dnlstffrd
Change combinatorix
So i know I need to use combinatorix for this, but I'm not exactly sure how.

4.3.19 In how many ways can you make change for a dollar, using pennies, nickels, dimes, quarters, and half-dollars? For example, 100 pennies is one way; 20 pennies, 2 nickels, and 7 dimes is another. Order doesn't matter.

• Aug 28th 2007, 08:41 AM
ThePerfectHacker
Did you try generating functions?

Let $a_n$ be the number of non-negative solutions to,
$x_1+5x_2+10x_3+25x_4+50x_5=n$.
Create the generating function,
$f(x) = a_0+a_1x+a_2x^2+...$.
Now, realize that,
$g_1(x)g_2(x)g_3(x)g_4(x)g_5(x) = f(x)$
Where,
$g_1(x)=1+x+x^2+...$
$g_2(x)=1+x^5+x^{10}+...$
$g_3(x)=1+x^{10}+x^{20}+...$
$g_4(x)=1+x^{25}+x^{50}+...$
$g_5(x)=1+x^{50}+x^{100}+...$
Thus, by geometric series,
$f(x) = \frac{1}{1-x}\cdot \frac{1}{1-x^5}\cdot \frac{1}{1-x^{10}}\cdot \frac{1}{1-x^{25}}\cdot \frac{1}{1-x^{50}}$

Does that work out?
• Aug 28th 2007, 08:41 AM
Plato
There is no easy way to do this problem!
The most efficient way is by generating functions.
Can you expand the following expression:
$\left( {\sum\limits_{k = 0}^{100} {x^k } } \right)\left( {\sum\limits_{k = 0}^{20} {x^{5k} } } \right)\left( {\sum\limits_{k = 0}^{10} {x^{10k} } } \right)\left( {\sum\limits_{k = 0}^4 {x^{25k} } } \right)\left( {\sum\limits_{k = 0}^2 {x^{50k} } } \right)$?

If you can then the coefficient of $x^{100}$ is the answer to the question.
• Aug 28th 2007, 09:08 AM
dnlstffrd
The highest term I got when multiplying all of that together was (3x^19)/(20(x^20-x^15+x^10-x^5+1)). Did I do something wrong?
• Aug 28th 2007, 01:44 PM
dnlstffrd
I'm still stuck on this one. I don't get an x^100 term when I do the product of the geometric series. What do I do?