Applications: Partition Problems and Coin Change
What you'll learn: How generating functions elegantly solve counting problems involving ways to partition integers and make change with coins.
The Core Idea
Generating functions transform counting problems into algebra. For integer partitions (writing a number as a sum of positive integers) and coin change (counting ways to make an amount using given denominations), we encode the problem as a product of series, then extract coefficients.
Integer Partitions
To count partitions of an integer n, consider that we can use any number of 1's, any number of 2's, etc. The generating function is:
Each factor corresponds to one integer we can use. The first factor allows using 0, 1, 2,... ones (contributing 0, 1, 2,... to the sum). The second allows 0, 1, 2,... twos (contributing 0, 2, 4,...).
Each factor is a geometric series: for integer k. So:
The coefficient of gives the number of partitions of n.
Coin Change
For coins of denominations , the generating function is:
Example: Ways to make change using pennies (1¢), nickels (5¢), and dimes (10¢):
The coefficient of tells you how many ways to make 25¢.
This approach works because each factor generates all possible contributions from that coin type, and multiplication combines independent choices.
Key Takeaway: Generating functions convert partition and coin-change problems into coefficient extraction from products of geometric series—turning a complex counting question into algebraic manipulation.