Course contentsShow
← Mathematics
Lesson 2646 of 3,12152. CombinatoricsFree lesson

Applications: Partition Problems and Coin Change

Apply generating functions to integer partition and coin change counting problems.

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:

G(x)=(1+x+x2+x3+⋯ )(1+x2+x4+⋯ )(1+x3+x6+⋯ )⋯G(x) = (1 + x + x^2 + x^3 + \cdots)(1 + x^2 + x^4 + \cdots)(1 + x^3 + x^6 + \cdots)\cdots

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: 11−xk\frac{1}{1-x^k} for integer k. So:

G(x)=∏k=1∞11−xkG(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^k}

The coefficient of xnx^n gives the number of partitions of n.

Coin Change

For coins of denominations d1,d2,…,dmd_1, d_2, \ldots, d_m, the generating function is:

G(x)=1(1−xd1)(1−xd2)⋯(1−xdm)G(x) = \frac{1}{(1-x^{d_1})(1-x^{d_2})\cdots(1-x^{d_m})}

Example: Ways to make change using pennies (1¢), nickels (5¢), and dimes (10¢):

G(x)=1(1−x)(1−x5)(1−x10)G(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})}

The coefficient of x25x^{25} 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.