# help me in solving this

• Dec 11th 2008, 10:10 AM
kkkkkk
help me in solving this
Find a closed form expression (i.e., a rational function) for the generating function for the number of ways to make n cents out of nickels, dimes and quarters if you must use an even number of nickels, an odd number of dimes, at least 2 quarters, at most 20 nickels, and at most 12 dimes? Expand the expression showing all nonzero terms through x100. Note: The number of such ways for 80 cents and 85 cents is 2 and 1, respectively
• Dec 13th 2008, 01:51 PM
awkward
Quote:

Originally Posted by kkkkkk
Find a closed form expression (i.e., a rational function) for the generating function for the number of ways to make n cents out of nickels, dimes and quarters if you must use an even number of nickels, an odd number of dimes, at least 2 quarters, at most 20 nickels, and at most 12 dimes? Expand the expression showing all nonzero terms through x100. Note: The number of such ways for 80 cents and 85 cents is 2 and 1, respectively

I'll try to get you started.

The ordinary power series generating function for the value of an even number of nickels,at most 20, is
$\displaystyle \sum_{i=0}^{10} x^{5 \cdot 2i}$

for an odd number of dimes, at most 12 (i.e., at most 11)
$\displaystyle \sum_{j=0}^{5} x^{10 (2j+1)}$

for at least 2 quarters,
$\displaystyle \sum_{k=2}^\infty x^{25k}$

Multiply those three series together and you have the generating function for the number of ways to make change using the specified coins. You will have to sum the series involved in order to get your answer in the form of a rational function.