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

In summary: Now, the term y^(2+3) x^(2a+3b) correspond withusing 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,and the factor (1+x^a) for each a enforcing use of an even number of coins of that part.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
  • #1
saubbie
13
0

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
 
Physics news on Phys.org
  • #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 + ..)
 

What is the definition of "Number of ways to make change for dollar with even number of coins"?

The "Number of ways to make change for dollar with even number of coins" refers to the total number of unique combinations of coins that can be used to make exactly one dollar, where the number of coins used is an even number.

Why is finding the number of ways to make change for a dollar with an even number of coins important?

This calculation is important in various fields such as computer science, economics, and game theory. It helps in understanding the complexity and efficiency of algorithms, analyzing economic transactions, and strategizing in games involving coins or currency.

What is the formula for calculating the number of ways to make change for a dollar with an even number of coins?

The formula for calculating the number of ways to make change for a dollar with an even number of coins is:
N = (a+b+c+d+...)^2 + (a+b+c+d+...)(a+b+c+d+...-1)
Where a, b, c, d, etc. represent the number of each type of coin used. This formula can be simplified and generalized for any currency and any target amount.

Can the number of ways to make change for a dollar with an even number of coins be calculated using a computer program?

Yes, the calculation can be easily done using a computer program. This problem can be solved using dynamic programming techniques, where the number of ways is built up incrementally using previously calculated values. This approach is more efficient than a brute-force method and can handle larger numbers of coins and target amounts.

What are some applications of the "Number of ways to make change for dollar with even number of coins" problem?

Some applications of this problem include:

  • Designing efficient algorithms for making change in vending machines or cashiers.
  • Analyzing the complexity and efficiency of different algorithms in computer science.
  • Studying economic transactions and analyzing the impact of currency denominations on transactions.
  • Developing strategies in games involving coins or currency.

Similar threads

  • Calculus and Beyond Homework Help
Replies
23
Views
3K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
894
  • Calculus and Beyond Homework Help
Replies
10
Views
5K
  • Calculus and Beyond Homework Help
Replies
3
Views
164
  • Calculus and Beyond Homework Help
Replies
2
Views
848
  • Calculus and Beyond Homework Help
Replies
14
Views
860
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top