Three Results on Making Change (An Exposition)

2015/07/16 by William Gasarch, Gasarch, William, Naveen Raman +1
Engineering · Mathematics · #11P81 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems #math.CO #msc:11P81

paper · pdf · doi:10.48550/arxiv.1507.04421

openalex publication_date 2015/07/16 · arxiv created 2016/01/08 · arxiv updated 2016/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Assume you an infinite supply of pennies, nickels, dimes, and quarters (or some other finite set of denominations which are relatively prime). Let CH(n) be the number of ways to make change of n cents. We present a simple unified exposition of three know theorems about CH(n). Let M be the LCM of a1,...,aL. Let M' be the LCM of the GCD of all pairs of ai's. (1) If 0≤ r≤ M-1 then CH(n) restricted to n ≡ r mod M is a poly, (2) If 0≤ r≤ M'-1 then CH(n) restricted to n≡ r mod M' is a poly except for the constant term, (3) CH(n) is n^L-1/(L-1)!a1a2...aL + O(n^L-2). Part (3) is known as Schur's theorem.

Related

• How many ways can you make change: Some easy proofs
• The change-making problem for six coin values and beyond
• Characterization of canonical systems with six types of coins for the change-making problem
• Partition Identities and the Coin Exchange Problem
• In How many ways can I carry a total of n coins in my two pockets, and have the same amount in both pockets?