Coin Change Problem

Combinatorics · Axiom Academy

REAL WORLD Coin Change Problem How generating functions solve a classic programming challenge You're at a convenience store, and the cashier needs to give you 11 cents in change. They have pennies (1¢), nickels (5¢), and dimes (10¢) available. How many different ways can they make this change? This isn't just a curiosity—it's a fundamental problem in computer science called the Coin Change Problem . It appears in: Let's use generating functions —a powerful tool from combinatorics—to solve this elegantly! Let's start by exploring different amounts. Use the controls below to see how many ways you can make change for different amounts: Notice how quickly the number of ways grows? For 11 cents, there are 4 ways . For 25 cents, there are 13 ways . This combinatorial explosion is exactly why we need a smart mathematical approach! Before we dive into the solution, let's think about the structure of this problem: What makes this a combinatorics problem? Think about what we're really counting... Generating Functions to the Rescue Here's where the magic happens. We represent each coin type as an infinite series : You can use 0, 1, 2, 3, ... pennies You can use 0, 1, 2, 3, ... nickels (each worth 5¢) You can use 0, 1, 2, 3, ... dimes (each worth 10¢) The coefficient of x n in each series tells us how many ways to make n cents using only that coin type. To count ways using all coin types, we multiply these generating functions:

This is the written version of the interactive lesson above. See the full Combinatorics course.