In how many ways can 45 cents be made using any combination of quarters, dimes, nickels, and pennies?
q = quarters, d = dimes, n = nickels, p = pennies
Only 1 quarter:
1q + 2d
1q + 1d + 2n
1q + 1d + 1n + 5p
1q + 1d + 10p
1q + 4n
1q + 3n + 5p
1q + 2n + 10p
1q + 1n + 15p
1q + 20p
9 ways
No quarter:
4d + 1n
4d + 5p
3d + 3n
3d + 2n + 5p
3d + 1n + 10p
3d + 15p
2d + 5n
2d + 4n + 5p
2d + 3n + 10p
2d + 2n + 15p
2d + 1n + 20p
2d + 25p
1d + 7n
1d + 6n + 5p
1d + 5n + 10p
1d + 4n + 15p
1d + 3n + 20p
1d + 2n + 25p
1d + 1n + 30p
1d + 35p
9n
8n + 5p
7n + 10p
6n + 15p
5n + 20p
4n + 25p
3n + 30p
2n + 35p
1n + 40p
45p
30 ways
30 + 9 = 39 ways