# Thread: How many ways you can make change for an amount N !

1. ## How many ways you can make change for an amount N !

Hello,

I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1.
Any idea how to solve this? It reminds me combinatorial class and generating functions. I would be grateful for any help!

2. ## Re: How many ways you can make change for an amount N !

You only have the two coins of values "A" and "B"? The making change for amount "N" is asking for integers x and y such that Ax+ By= N. That is a "Diophantine equation" since it must be solved for integer x and y. This is more "number theory" than combinatorics,

There is a standard method of solving linear Diophantine equations. That is to first solve Ax+ By= 1, then multiply solutions by N. The "Euclidean algorithm" gives a means of solving Ax+ By= 1, in integers as long as GCD(A, B)= 1, as given here. (If GCD(A, B) is NOT 1 it is impossible for there to be integer x and y such that Ax+ By= 1 since GCD(A, B) would be a factor of the left side but not the right.)

For example, if A= 5 and B= 12, to solve 15x+ 22y= 37 (those numbers are made up arbitrarily), start by solving 15x+ 22y= 1. To do that I use the "Euclidean algorithm". I note that 15 divides into 22 once with remainder 7: 22- 15= 7. Then I note that 7 divides into 15 twice with remainder 1: 15- 2(7)= 1. (Since GCD(A, B)= 1 this method of dividing the preceding divisor by the preceding remainder will eventually give a remainder of 1.)

Replace the "7" in 15- 2(7)= 1 with its expression from the previous equation: 7= 22- 15. We have 15- 2(22- 15)= 3(15)- 2(22)= 1. That tells us immediately the one solution to 15x+ 22y= 1 is x= 3 and y= -2.

Now multiply x and y by N: x= 3N and y= -2N. They now satisfy 15x+ 22y= 15(3N)+ 22(-2N)= N. Further, it is easy to see that, for any integer ix, x= 3N- 22i and y= -2N+ 15i satisfy 15x+ 22y= 15(3N- 22i)+ 22(-2N+ 15i)= 45N- (15)(22i)- 44N- 22(15i)= N.

To get positive x and y, we must have 3N- 22i> 0 and -2N+ 15i> 0. That is, we must have i< (3/22)N and i> (2/15)N. The problem is now to determine values of N for which the interval (2/15)N to (3/22)N contains at least one integer. That, in turn, will certainly be true as long as (3/22)N- (2/15)N= (3/22- 2/15)N is greater than 1 but may be true for smaller N. Of course 3/22- 2/15= 1/330.

We can make change, with 15 and 22 value coins for any N larger than or equal to 330. Obviously we cannot make change for any value less than 15 but we can make change for N= 15. We cannot make change for N between 15 and 22 but can make change for N= 22. We cannot make change for any N between 22 and 15+ 22= 37 but can make change for 37. We cannot make change for any N between 37 and 2(15)+ 22= 52 but can make change for 52. We cannot make change for any N between 52 and 15+ 2(22)= 59 but can make change for 59. Continuing that way is tedious but the point of solving the Diophantine equation is that we know we can stop at N= 330 since we know we can make change for any N equal to or above 330.

3. ## Re: How many ways you can make change for an amount N !

Hmm i mentioned about generating functions beacuse it was presented as useful tool for finding out on how many ways u can make change for N with given currency.

4. ## Re: How many ways you can make change for an amount N !

Ty for giving algorythm for solving this problem, unfortunately it only shows me how find the solution by myself for any N,A,B given. I looking for the homogeneous formula. I found somewhere that all ways of making change are presented by the following function G(x)=1/((1-x^A)(1-x^B))