How many ways are there to make change for a $100 bill using $1, $5, $10, $20 and $50 bills?

Question

NOTE TO aman
You misinterpreted the question. 100 $1 bills is ONE way, 20 $5's is ONE way, 10 $10's is ONE way, (a $50, 2 $20's, 1 $5 & 5 $1's is ONE way) etc.

Answer 1

There are exactly 343 combinations. I can list them all, but others have already cluttered this thread quite well on their own. ^.^

You can think of the solution set as a series of tiered combinations. These would start with those sets beginning with a $50 bill, which can contain up to 2 x $50, 2 x $20, 5 x $10, etc. which I believe someone has started already in this thread. Or group them as pairs, triplets, etc. with the equation 50j+20k+10l+5m+1n=100, which may be a bit easier for calculations. Or a convergent series, where A=(ways to form $5), B=(ways to form $10, including A-sets), etc. With any method, find the different combinations for each set, then add them all up.

Doing this is still tedious and prone to mistakes, and thus probably not much of an improvement over manually listing all of the combinations one by one. It can also quickly become an insane exercise for larger values (for example, add the $2 bill, or find change for $200, or even worse). So instead of trying to think this problem through mathematically, I found it much easier to think it through as a programming problem. It lends itself very readily to a simple recursive subroutine using the following pseudocode:

make an empty stack
set total combinations to 0
call CheckCurrency
print total combinations found

recursive subroutine CheckCurrency
- if total currency in stack = 100
- - add 1 to the total combinations
- - (optional: display stack contents)
- - end recursion
- if total currency in stack > 100
- - end recursion
- if total currency in stack < 100, then
- - for each valid denomination (50,20,10,5,1)
- - - if the denomination < = smallest denomination in the stack
- - - - push it to the stack
- - - - call CheckCurrency
- - - - pop it from the stack
end of subroutine

This required only a few minutes to design, another few minutes to code, another few minutes to debug, less than 2 seconds to run, and has the wonderful bonus of being able to display every single combination if desired. It would also be trivial to modify it so that, for example, you can find all combinations if you also include the $2 bill. (The answer is: 4562 combinations.) Or to find all combinations totalling $200. (The answer is: 2930 combinations.)

The line that checks if the denomination is less than or equal to the smallest denomination currently in the stack is present to avoid a common mistake: We want the total combinations, not total permutations. Otherwise, the stack "50 20 20 10" would be counted differently than the stacks "50 20 10 20" and "50 10 20 20", and even "10 20 20 50". The total permutations is much, much greater, especially if you consider each bill as unique. Five $20 dollar bills alone have 5!=120 permutations because, after all, they are all completely different $20 bills. Imagine the number of permutations of 100 x $1 bills, and everything in between. o.O

Answer 2

Largest Bill being $50:
2 $50's
1 $50, 2 $20's, 1 $10
1 $50, 2 $20's, 2 $5's
1 $50, 2 $20's, 1 $5, 5 $1's
1 $50, 2 $20's, 10 $1's
1 $50, 1 $20, 3 $10's
1 $50, 1 $20, 2 $10's, 10 $1's
1 $50, 1 $20, 2 $10's, 2 $5's
1 $50, 1 $20, 2 $10's, 1 $5, 5 $1's
1 $50, 1 $20, 1 $10, 20 $1's
1 $50, 1 $20, 1 $10, 4 $5's
1 $50, 1 $20, 1 $10, 3 $5's, 5 $1's
1 $50, 1 $20, 1 $10, 2 $5's, 10 $1's
1 $50, 1 $20, 1 $10, 1 $5's, 15 $1's
1 $50, 1 $20, 6 $5's
1 $50, 1 $20, 5 $5's, 5 $1's
1 $50, 1 $20, 4 $5's, 10 $1's
1 $50, 1 $20, 3 $5's, 15 $1's
1 $50, 1 $20, 2 $5's, 20 $1's
1 $50, 1 $20, 1 $5, 25 $1's
1 $50, 1 $20, 50 $1's
1 $50, 5 $10's
1 $50, 4 $10's, 2 $5's
1 $50, 4 $10's, 1 $5, 5 $1's
1 $50, 4 $10's, 10 $1's
1 $50, 3 $10's, 4 $5's
1 $50, 3 $10's, 3 $5's, 5 $1's
1 $50, 3 $10's, 2 $5's, 10 $1's
1 $50, 3 $10's, 1 $5's, 15 $1's
1 $50, 3 $10's, 20 $1's
1 $50, 2 $10's, 6 $5's
1 $50, 2 $10's, 5 $5's, 5 $1's
1 $50, 2 $10's, 4 $5's, 10 $1's
1 $50, 2 $10's, 3 $5's, 15 $1's
1 $50, 2 $10's, 2 $5's, 20 $1's
1 $50, 2 $10's, 1 $5's, 25 $1's
1 $50, 2 $10's, 30 $1's
1 $50, 1 $10, 8 $5's
1 $50, 1 $10, 7 $5's, 5 $1's
1 $50, 1 $10, 6 $5's, 10 $1's
1 $50, 1 $10, 5 $5's, 15 $1's
1 $50, 1 $10, 4 $5's, 20 $1's
1 $50, 1 $10, 3 $5's, 25 $1's
1 $50, 1 $10, 2 $5's, 30 $1's
1 $50, 1 $10, 1 $5's, 35 $1's
1 $50, 1 $10, 40 $1's
1 $50, 10 $5's
1 $50, 9 $5's, 5 $1's
1 $50, 8 $5's, 10 $1's
1 $50, 7 $5's, 15 $1's
1 $50, 6 $5's, 10 $1's
1 $50, 5 $5's, 25 $1's
1 $50, 4 $5's, 30 $1's
1 $50, 3 $5's, 35 $1's
1 $50, 2 $5's, 40 $1's
1 $50, 1 $5's, 45 $1's
1 $50, 50 $1's

Largest Bill being $20:
5 $20's
4 $20's, 2 $10's
4 $20's, 1 $10, 2 $5's
4 $20's, 1 $10, 1 $5, 5 $1's
4 $20's, 1 $10, 10 $1's
3 $20's, 4 $10's
3 $20's, 3 $10's, 2 $5's
3 $20's, 3 $10's, 1 $5, 5 $1's
3 $20's, 3 $10's, 10 $1's
3 $20's, 2 $10's, 4 $5's
3 $20's, 2 $10's, 3 $5's, 5 $1's
3 $20's, 2 $10's, 2 $5's, 10 $1's
3 $20's, 2 $10's, 1 $5's, 15 $1's
3 $20's, 2 $10's, 20 $1's
3 $20's, 1 $10, 6 $5's
3 $20's, 1 $10, 5 $5's, 5 $1's
3 $20's, 1 $10, 4 $5's, 10 $1's
3 $20's, 1 $10, 3 $5's, 15 $1's
3 $20's, 1 $10, 2 $5's, 10 $1's
3 $20's, 1 $10, 1 $5's, 25 $1's
3 $20's, 1 $10, 30 $1's
2 $20's, 6 $10's
2 $20's, 5 $10's, 2 $5's
2 $20's, 5 $10's, 1 $5, 5 $1's
2 $20's, 5 $10's, 10 $1's
2 $20's, 4 $10's, 4 $5's
2 $20's, 4 $10's, 3 $5's, 5 $1's
2 $20's, 4 $10's, 2 $5's, 10 $1's
2 $20's, 4 $10's, 1 $5's, 15 $1's
2 $20's, 4 $10's, 20 $1's
2 $20's, 3 $10's, 6 $5's
2 $20's, 3 $10's, 5 $5's, 5 $1's
2 $20's, 3 $10's, 4 $5's, 10 $1's
2 $20's, 3 $10's, 3 $5's, 15 $1's
2 $20's, 3 $10's, 2 $5's, 20 $1's
2 $20's, 3 $10's, 1 $5's, 25 $1's
2 $20's, 3 $10's, 30 $1's
2 $20's, 2 $10's, 8 $5's
2 $20's, 2 $10's, 7 $5's, 5 $1's
2 $20's, 2 $10's, 6 $5's, 10 $1's
2 $20's, 2 $10's, 5 $5's, 15 $1's
2 $20's, 2 $10's, 4 $5's, 20 $1's
2 $20's, 2 $10's, 3 $5's, 25 $1's
2 $20's, 2 $10's, 2 $5's, 30 $1's
2 $20's, 2 $10's, 1 $5's, 35 $1's
2 $20's, 2 $10's, 40 $1's
2 $20's, 1 $10, 10 $5's
2 $20's, 1 $10, 9 $5's, 5 $1's
2 $20's, 1 $10, 8 $5's, 10 $1's
2 $20's, 1 $10, 7 $5's, 15 $1's
2 $20's, 1 $10, 6 $5's, 20 $1's
2 $20's, 1 $10, 5 $5's, 25 $1's
2 $20's, 1 $10, 4 $5's, 30 $1's
2 $20's, 1 $10, 3 $5's, 35 $1's
2 $20's, 1 $10, 2 $5's, 40 $1's
2 $20's, 1 $10, 1 $5's, 45 $1's
2 $20's, 1 $10, 50 $1's
2 $20's, 12 $5's
2 $20's, 11 $5's, 5 $1's
2 $20's, 10 $5's, 10 $1's
2 $20's, 9 $5's, 15 $1's
2 $20's, 8 $5's, 20 $1's
2 $20's, 7 $5's, 25 $1's
2 $20's, 6 $5's, 30 $1's
2 $20's, 5 $5's, 35 $1's
2 $20's, 4 $5's, 40 $1's
2 $20's, 3 $5's, 45 $1's
2 $20's, 2 $5's, 50 $1's
2 $20's, 1 $5's, 55 $1's
2 $20's, 60 $1's
1 $20, 8 $10's....etc

I have illustrated 128 ways...there are many more. Continue on with the same pattern. Then start with largest bill being 10, then 5, then 1

Answer 3

50 50
50 20 20 10
50 20 20 5 5
50 20 20 5 1 1 1 1 1
50 20 10 10 10
50 20 10 10 5 5
50 20 10 10 5 1 1 1 1 1
50 20 10 10 1 1 1 1 1 1 1 1 1 1
50 20 10 5 5 5 5
50 20 10 5 5 5 1 1 1 1 1
50 20 10 5 5 1 1 1 1 1 1 1 1 1 1
50 20 10 5 (15 x $1)
50 20 10 (20 x $1)
50 20 5 5 (20 x $1)
50 20 5 (25 x $1)
50 20 (30 x $1)
50 10 10 10 10 10
50 10 10 10 10 5 5
50 10 10 10 10 5 (5x$1)
50 10 10 10 10 (10 x $1)
50 10 10 10 5 5 5 5
50 10 10 10 5 5 5 (5x$1)
50 10 10 10 5 5 (10x$1)
50 10 10 10 5 (15x$1)
50 10 10 10 (20x$1)
50 10 10 5 5 5 5 5 5
50 10 10 5 5 5 5 5 (5 x $1)
50 10 10 5 5 5 5 (10x$1)
50 10 10 5 5 5 (15x$1)
50 10 10 5 5 (20x$1)
50 10 10 5 (25x$1)
50 10 10 (30 x $1)
50 10 5 5 (30 x $1)
50 10 5 (35 x $1)
50 10 (40 x $1)
50 5 5 5 5 5 5 5 5 5 5
50 5 5 5 5 5 5 5 5 5 (5x$1)
50 (8x$5) (10x$1)
50 (7x$5) (15x$1)
50 (6x$5) (20x$1)
50 (5x$5) (25x$1)
50 (4x$5) (30x$1)
50 (3x$5) (35x$1)
50 5 5 (40x$1)
50 5 (45x$1)
50 (50x$1)

20 20 20 20 20
20 20 20 20 10 10
20 20 20 20 10 5 5
20 20 20 20 10 5 1 1 1 1 1
20 20 20 20 10 (10x$1)
20 20 20 20 5 5 (10x$1)
20 20 20 20 5 (15x$1)
20 20 20 20 (20x$1)
20 20 20 10 10 10 10
20 20 20 10 10 10 5 5
20 20 20 10 10 10 5 (5x$1)
20 20 20 10 10 10 (10x$1)
20 20 20 10 10 5 5 5 5
20 20 20 10 10 5 5 5 (5x$1)
20 20 20 10 10 5 5 (10x$1)
20 20 20 10 10 5 (15x$1)
20 20 20 10 10 (20x$1)
20 20 20 10 (6x$5)
20 20 20 10 (5x$5) (5x$1)
20 20 20 10 (4x$5) (10x$1)
20 20 20 10 (3x$5) (15x$1)
20 20 20 10 (2x$5) (20x$1)
20 20 20 10 5 (25x$1)
20 20 20 10 (30x$1)
20 20 20 5 5 (30x$1)
20 20 20 5 (35x$1)
20 20 20 (40x$1)



etc etc

loads and loads of ways

Answer 4

wow.. kinda difficult question but i guess it can be solved by this way ... 5 x 4 x 3 x 2 x 1 = 120...
5 come from only using same notes e.g. 100 $1 notes, 20 $5 notes, and so on...
4 come from combination $50 note with the others notes. e.g. 1 $50 note and 50 $ 1 notes..
3 come from 3 combination different notes...
2 come from 4 combination different notes...
and so on... but i'm not quite sure with this way... because it's quite difficult to prove...

Answer 5

I get 343 ways

Set up the equation:

1a+5b+10c+20d+50e = 100

Anywhere up to 4 of the variables a,b,c,d,e can be 0.
Since 100 is divisible by 50,20,10,5,1 we have 5 ways of changing $100 with no mixed bills.(i.e. 4 variables 0)
However, we can have 0,1,2 or 3 variables set to zero in a variety of ways which will give unique divisions of 100.

Let d(a,b,c..) be the number of ways 100 can be changed using at least one of a,b,c,.. and no others.

Then, for example d(20,50) = 0 since there must be at least one 50 and one 20, and so there's no solution.

It's easy to see how to compute d(1,5), for example, since 100/5 = 20 we can use anywhere from 1 to 19 5s (we can't have all 5s or all 1s) So d(1,5) = 19
Many of the following will obviously be equal but are listed.
Ten distinct pairings: Total = 52
d(1,5) =19
d(1,10) = 9
d(1,20)= 4
d(1,50) = 1
d(5,10) = 9
d(5,20) = 4
d(5,50)= 1
d(10,20) = 4
d(10,50) =1
d(20,50) = 0
Ten distinct triplets: Total= 172
d(1,5,10) = 17+15+13+11+9+7+5+3+1 = 81
Notice we have 9 terms (1 to 9 tens)
d(1,5,20) = 15+11+7+3 = 36
d(1,5,50) = 9
d(1,10,20)= 7+5+3+1 = 16
d(1,10,50)= 4
d(1,20,50) = 2
d(5,10,20) = 7+5+3+1 =16
d(5,10,50) = 4
d(5,20,50)= 2
d(10,20,50)=2
Five quads: total = 110
d(1,5,10,20) = 84
d(1,5,10,50) = 16
d(1,5,20,50) = 6
d(1,10,20,50) = 2
d(5,10,20,50) = 2
One quint.
d(1,5,10,20,50) = 4

Answer 6

$1 100 ways
$5 20 ways
$10 10 ways
$20 4 ways
$50 2 ways
add em up 136 and the rest i dunno but there are over 200 ways

Answer 7

over 100

Answer 8

a whole bunch but i'm to busy to count all of them

Answer 9

as long as you get $100.00 why worry about that?