How many ways can you make change: Some easy proofs

2014/06/19 by William Gasarch, Gasarch, William
Mathematics · #05A17 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #History and Overview (math.HO) #Mathematics and Applications #math.CO #math.HO #msc:05A17

paper · pdf · doi:10.48550/arxiv.1406.5213

openalex publication_date 2014/06/19 · arxiv created 2014/07/18 · arxiv updated 2014/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a dollar, how many ways are there to make change using pennies, nickels, dimes, and quarters? What if you are given a different amount of money? What if you use different coin denominations? This is a well known problem and formulas are known. We present simpler proofs in several cases. We use recurrences to derive formulas if the coin denominations are 1,x,kx,rx, and we use a simple proof using generating functions to derive a formula for any coin set.

Related

• The change-making problem for six coin values and beyond
• Three Results on Making Change (An Exposition)
• The Greedy Coin Change Problem
• Characterization of canonical systems with six types of coins for the change-making problem
• Canonical Coin Systems for Change-Making Problems