Using Generating Functions to Count Distributions
You'll learn how generating functions elegantly count the ways to distribute indistinguishable objects into distinct bins with constraints.
The Core Idea
Imagine you have a pile of identical coins and several labeled boxes. You want to count how many ways you can distribute these coins into the boxes, possibly with rules like "box A gets at most 3 coins" or "box B gets an even number."
Generating functions transform this counting problem into algebra. Each box gets its own factor in a product, where the exponents track how many objects go into that box, and the coefficients encode how many ways each distribution can happen.
How It Works
For box i that can receive objects according to some rule, write a generating function representing all possibilities:
- No restrictions: Box can hold 0, 1, 2, 3,... objects → factor is
(1 + x + x² + x³ + ...)=1/(1-x) - At most k objects:
(1 + x + x² + ... + xᵏ) - Exactly j objects:
xʲ - Even number:
(1 + x² + x⁴ + ...)=1/(1-x²)
The total generating function is the product of all box factors. The coefficient of xⁿ in the expanded product tells you how many ways to distribute exactly n objects total.
Example
Three distinct bins, unlimited capacity:
G(x) = (1 + x + x² + ...)(1 + x + x² + ...)(1 + x + x² + ...)
= 1/(1-x)³
Expanding gives coefficients matching C(n+2, 2) — the number of ways to put n indistinguishable objects into 3 distinct bins!
Key Takeaway: Generating functions convert distribution problems into products of power series; the coefficient of xⁿ counts distributions summing to n objects.