Ways to make a dollar with variable denominations

[soandos]

How many ways are there to make a dollar using coins of denominations of 1,4,7,15,33 cents each?
is there a formula that can generalize this for any set of given denominations?

 

[micromass]

This is the knapsack problem. I doubt that there is an easy formula for this. As for your first question, I fear that you'll have to check every possibility

 

[Bill Simpson]

In Graham, Knuth & Patashnki's "Concrete Mathematics" in chapter 7 shows how to use generating functions to solve problems exactly like this. Their example uses pennies, nickels, dimes, quarters and half dollars but the same steps should apply to your problem.

 

[soandos]

I saw this: "Take the taylor expansion of 1 over (1-x)*(1-x5)*(1-x10)*(1-x25)*(1-x50)*(1-x100), and jot down the coefficient of x100. This is the generating function for the ways to partition 100 into subsets of size 1, 5, 10, 25, 50, or 100, so there are 293 ways to make change for one us dollar." on answers.com, but i got a massive co-efficient for the Taylor expansion about x=1.
Is this what you were talking about?
and if so, can you please explain it?

 

[soandos]

It seems related to the knapsack problem, there there is no issue of weights, and the value is not to be maximized, but equal to a given number.

 

[Bacle]

Actually, this is also a variation on the idea of the multinomial coefficients:

when you do (a+b)^2 =a^2+2ab+b^2 , the 2 in 2ab is the number of ways

you can get a term with one a and one b in an expansion (a+b)(a+b): you

can choose the a in two ways, then the second term is determined.

Same for (a+b)^n =(a+b)(a+b)...(a+b) :

to see how many terms a^kb you can get ( 0<=k<=n, of course) : you can

select k a's out of the n possible ones in the product in nCk ways. This is

another way of seeing the binomial coefficients.

Now expand to the case of a multinomial ( x^1+x^10+...+x^25)^100

How many terms will add up to 100.?

 

[soandos]

(x + x^5 + x^10 + x^25 + x^50)^100. the x^100 co-efficient is one...
unless i messed up.

 

[Bill Simpson]

The description of how to understand and use generating functions in Graham, Knuth & Patashnki's "Concrete Mathematics" to solve this problem is probably too long to include here. It does show that there are 292 ways of making change for a dollar, but they do not include a dollar coin, so it is one less than your 293 ways.

If you find yourself interested in problem solving I highly recommend buying a copy of the book. There are lots of things you can learn from it. See if you can get a later edition and a later printing because, unlike Knuth's other books, there were a variety of small errors in the earlier versions of the book. There are errata lists on the net if you get an earlier version and you can go through and mark up your copy.

I only wish I could say that I had mastered a substantial fraction of all the material in the book or that I had been able to sit in the back of their class and learn the material from them.

 

[awkward]

Some observations that may be helpful:

1. The number of ways to make change for a dollar with coins of value 1, 4, 7, 15 and 33 is the same as the number of ways to make change for a dollar or less (including an amount of zero) with coins of value 4, 7, 15 and 33.

2. If you're doing this by pencil and paper, the most efficient method may be a recursive approach. I.e., you know there can only be 0, 1, 2, or 3 coins of value 33. So find the number of ways to make change for 1, 34, 67, or 100 cents with coins of value 1, 4, 7, and 15. Keep breaking the problem into smaller cases similarly. You can probably figure out how to organize your work in a table and work from the bottom up instead of the top-down (recursive) approach.

3. If you have access to a computer algebra package, consider the polynomials
P = 1 + x^{33} + x^{67}
Q = 1 + x^{15} + x^{30} + \dots + x^{90}
R = 1 + x^7 + x^{14} + \dots + x^{98}
S = 1 + x^4 + x^8 + \dots + x^{100}
Expand PQRS. The answer to the problem is the sum of the coefficients of the powers of x less than or equal to x^100 , by Observation 1. Or you could do this with pencil and paper, retaining only powers of x less than or equal to x^100 as you go along.

 

[soandos]

why is <br /> P = 1 + x^{33} + x^{67}<br />
as opposed to <br /> P = 1 + x^{33} + x^{66}<br />
?

 

[awkward]

why is <br /> P = 1 + x^{33} + x^{67}<br />
as opposed to <br /> P = 1 + x^{33} + x^{66}<br />
?

Oops, I should have written
<br /> P = 1 + x^{33} + x^{66} + x^{99}<br />

 

[soandos]

I got 824. Did i implement it correctly?

 

[Bill Simpson]

Using his PQRS technique I get 823 which is the sum of 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5, 5, 4, 5, 6, 6, 5, 6, 7, 6, 6, 7, 8, 7, 7, 8, 9, 8, 8, 10, 10, 9, 10, 11, 11, 10, 12, 12, 12, 12, 13, 14, 13, 14, 15, 15, 15, 16, 17, 16, 17, 18, 18, 18, 19, 20, 20, 20, 21, 22, 22, 22, 24, 24, 24, 24, 26. If you check off your coefficients against mine maybe you can find that you missed one, I missed one or we both missed something.

As a check I use his PQRS on nickels,dimes,quarters,halves and get 292 which matches the above mentioned value.

 

[awkward]

As a check, you might find it interesting to write a program which actually generates and counts the combinations. Something like

goal = 100
nways = 0

for x33 = 0 to floor(goal / 33)
  for x15 = 0 to floor((goal - 33 * x33) / 15)
    for x7 = 0 to floor((goal - 33 * x33 - 15 * x15) / 7)
      for x4 = 0 to floor((goal - 33 * x33 - 15 * x15 - 7 *x7) / 4)
         nways = nways + 1