Generating Function help

Oct 2012
92
0
san francisco
Hey there I need some help on what to do next for this problem.

In how many ways can you make change for a dollar using
pennies, nickels, dimes, quarters, and half-dollars?

so far I got
(1+x+x^2+x^3+...+x^100) <-- pennies
(1+x^5+x^10+x^15+....+x^100) <- nickels
(1+x^10+x^20+x^30+...+x^100) <- dimes
(1+x^25+x^50+x^75+x^100) <- quarters
(1+x^50+x^75+x^100) <- half dollars

and the generating function is
1/(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)

what do I do from here to get the answer I need?
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Hey gfbrd.

What does this function refer to? Are you trying to solve a recurrence relation? Is this function meant to be equal to 0 where you need to find the roots?
 
Oct 2012
92
0
san francisco
sorry but i dont think i did anything wrong here, all i want to know is how do i get the coefficient for x^100 from the generating function
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Ohh I see what you are trying to do.

Try expanding out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look at the generating function for (1-x) when you get these terms multiplied by the expansion to give x^100 (there should be 16 terms to look for) then collect the coeffecients together.
 
Oct 2012
92
0
san francisco
what do you mean by expanding?
do I multiply this out?

(1+x+x^2+x^3+...+x^100)(1+x^5+x^10+x^15+....+x^100)(1+x^10+x^20+x^30+...+x^100)(1+x^25+x^50+x^75+x^100)(1+x^50+x^75+x^100)
if so how do I multiply this out, it would take forever to do it by hand
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
No don't do that: multiply out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look for when x^n * all the individual terms in the expanding polynomial give an x^100 term and collect those terms together.

Your generating function will be in terms of a_n*x^n so all you need to check are the terms where a_n*x^n * blah*x^k give a_n*blah*x^(n+k) where n+k = 100.
 
Oct 2012
92
0
san francisco
ok i expanded it and i got

1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90

i dont really see any x^100 terms here
im not sure what do i really do next sorry im a bit slow on this
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Now you have to consider (1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90)*a_n*x^n where all these terms have a x^100 term in them.

For example 1*a_n*x^n has n = 100, while -x^5*a_n*x^n has n = 95 and so on.
 
Oct 2012
92
0
san francisco
going from left to right i get n=100,n=95,n=90,n=85,n=75,n=70,n=65,n=60,n=50,n=45,n=40,n=35,n=25,n=20,n=15,n=10
but what do i do with these terms though? sorry i need to take this slowly to understand
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Now you need to consider what the a_n's are for those terms and then add them up.

Remember that these terms are the only time the whole series if were expanding out as a generating function gave a b_n*x^n where n = 100 where this is for the full expanding series.

Since you have all the possible terms where the n = 100 for the b_n, then the b_n for the expanding series will be the same of all the a_n's in your 1/(1-x) that correspond to those terms which means if you find all the a_n's and multiply them by the coffecients in the polynomial you just expanded then you will get the b_100 term which is the coffecient of the generating series for n = 100.

A few examples might clear things up:

1*a_100 for the first term
-a_5 for the second term
-a_10 for the third term

and so on

and then the final coffecient will be the sum of all these terms since all these terms have the common x^100 term if you looked at the completely expanding generator function with x^100*b_100 (you are trying to find b_100).