Number of ways to make change for dollar with even number of coins

[saubbie]

Homework Statement

I need to find the number of ways to make change for a dollar using an even number of coins, using only pennies, nickels, dimes, quarters, and fifty cent pieces.

Homework Equations

I found the generating function for the ways of making change for a dollar, 1/(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50).

The Attempt at a Solution

I was thinking of changing the x into an x/2 to ensure that each number of coins is even, but I know that is not right. I am not sure how to ensure that there are an even number of coins. I need to find a new generating function, but am not sure what it is. Any help is appreciated. Thanks

 

[alphachapmtl]

I have part of a solution. At least, it shows a way to attack the problem.

With parts 1,5,10,25,50, we have:
1 / (1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)
=
(1+x+x^2+x^3+..)(1+x^5+x^10+x^15+..)(1+x^10+x^20+x^30+..)(1+x^25+x^50+x^75+..)(1+x^50+x^100+x^150+..)

Now, just to shorten the notation, let's consider parts a,b only.
It would generalise in the obvious way.

With parts a,b, we have:
1 / (1-x^a) (1-x^b)
=
(1+x^a+x^2a+x^3a+..) (1+x^b+x^2b+x^3b+..)

Here, the term x^(2a+3b) correspond with using a,a,b,b,b coins (summing to 2a+3b).
The exponent of x here being the sum of the parts.
So when we expand the gf (generating function) in x,
the coefficient of x^s is the number of ways to get a sum of s.
=====
Now we need to count those parts, getting the number 5.
To do that , it is best to use another variable, y.

So instead of (1 + x^a + x^2a + x^3a + ..),
we can use (1 + y x^a+ y^2 x^2a + y^3 x^3a + ..)

So with parts a,b, we have:
1 / (1 - y x^a) (1 - y x^b)
=
(1 + y x^a y + y^2 x^2a + y^3 x^3a + ..) (1 + y x^a y + y^2 x^2a + y^3 x^3a + ..)

Now, the term y^(2+3) x^(2a+3b) correspond with using a,a,b,b,b coins (counting to 2+3, summing to 2a+3b)
The exponent of y here being the number of parts.
The exponent of x here being the sum of the parts.
So when we expand the gf (generating function) in y and x,
the coefficient of y^c x^s is the number of ways to get a count of c and a sum of s .
=====
but we want an even number of coins, so we only need to count the parts modulo 2.
Instead of counting 0,1,2,3,.. we have to count 0,1,0,1,..

So instead of (1 + y x^a+ y^2 x^2a + y^3 x^3a + ..),
we can use (1 + y x^a+ x^2a + y x^3a + ..)
or (1 + x^2a + x^4a + ..) + (y x^a+ y x^3a + y x^5a ..)
or (1 + x^2a + x^4a + ..) + y (x^a+ x^3a + x^5a ..)
or (1 + x^2a + x^4a + ..) + y x^a (1+ x^2a + x^4a ..)
or (1 + y x^a) (1+ x^2a + x^4a ..)
or (1 + y x^a) / (1-x^2a)

So with parts a,b, we have:
(1 + y x^a) (1 + y x^b) / (1-x^2a) (1-x^2b)
=
(1 + y x^a y + x^2a + y x^3a + ..) (1 + y x^a y + x^2a + y x^3a + ..)