3.6Generating functions
The idea
A generating function packs a sequence into a power series Σ aₙxⁿ. Multiplying the series of independent choices counts the ways to total n: the coefficient of xⁿ is the answer.
Think of it like this: A coat rack: the coefficient is the number of coats hanging on peg n; combining racks multiplies their patterns.
Why it exists
It gives a clean way to count selections with limits (coins, dice, distributions) and to solve recurrences.
How it works
- 1/(1−x) = 1 + x + x² + … : one way for every n.
- (1+x)ᵐ: the coefficient of xⁿ is C(m, n).
- 1/(1−x)ᵐ: the coefficient of xⁿ is C(n+m−1, n) (stars and bars).
- Independent choices multiply their series; the answer is the coefficient of xⁿ in the product.
Worked example: Ways to make 6 using coins of 1 and 2
Coefficient of x⁶ in 1/((1−x)(1−x²)) is ⌊6/2⌋ + 1 = 4.
Now play with it
- →Load the 1-and-2 coins function and read the coefficient row.
- →Add the 5-coin function and see how the counts grow.
| x^0 | x^1 | x^2 | x^3 | x^4 | x^5 | x^6 | x^7 | x^8 | x^9 | x^10 | x^11 | x^12 | x^13 | x^14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 7 | 7 | 8 |
ways to make k using 1s and 2s: ⌊k/2⌋ + 1. Multiply the series of independent choices; the coefficient of xᵏ counts the ways to total k.
Check yourself
The coefficient of x⁴ in 1/(1−x)³ is
Exam notes (the dense version)
The generating function of a₀, a₁, … is Σ aₙxⁿ. 1/(1−x) gives all 1s; (1+x)ᵐ gives C(m,n); 1/(1−x)ᵐ gives C(n+m−1,n); xᵏ/(1−x) shifts. Independent choices multiply their series; the coefficient of xᵏ is the number of ways to total k. Solving a recurrence: multiply by xⁿ, sum, solve for G(x), expand by partial fractions.
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.