1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 17, 2008 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant 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).

    3. 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
     
  2. jcsd
  3. Sep 22, 2008 #2
    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 + ..)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number of ways to make change for dollar with even number of coins
  1. Prove a Number is Even (Replies: 5)

Loading...