Generating Functions

Hard5–6 hrsGenerating FunctionsPower SeriesRecurrencesClosed Form

Overview

Generating functions convert combinatorial sequences and recurrences into algebraic objects. The trick: multiply aₙ by xⁿ and sum, then translate the recurrence into an equation for G(x). Solving algebraically and expanding back gives the closed form. Generating functions unify three separate techniques: solving recurrences, counting with constraints, and computing moments of distributions. In quant contexts, probability generating functions are used to compute moments and characterize distributions defined recursively (like branching processes).

How to Recognize

→You have a recurrence and need a closed form
→Counting problems with an algebraic structure
→'How many ways to...' with a sum constraint and varying parts
→Solving linear recurrences with variable coefficients
→Probability distributions defined recursively

Step-by-Step Approach

1.Define G(x) = Σ aₙ xⁿ (ordinary generating function, OGF)
2.Translate recurrence into algebraic equation for G(x)
3.Solve for G(x) — usually a rational function
4.Partial fractions → read off aₙ from known series (1/(1-αx) = Σ αⁿxⁿ)
5.For probability: pgf G(x) = E[x^X] → G'(1) = E[X], G''(1) = E[X(X-1)]

Key Formulas

G(x) = \sum_{n=0}^\infty a_n x^n

— ordinary generating function

\frac{1}{1-x} = 1 + x + x^2 + \cdots = \sum x^n

\frac{1}{(1-x)^k} = \sum_n \binom{n+k-1}{k-1} x^n

— stars-and-bars generating function

E[X] = G'(1),\; E[X^2] - E[X] = G''(1)

— for probability generating functions

Worked Examples

0Quick Example

Fibonacci: Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀=0, F₁=1. G(x) = x/(1-x-x²). Partial fractions: G(x) = [1/√5][1/(1-φx) - 1/(1-ψx)]. Coefficient: Fₙ = (φⁿ - ψⁿ)/√5 where φ=(1+√5)/2.

Problem

How many ways can you make change for n cents using pennies (1¢) and nickels (5¢)?

Solution

Let aₙ = number of ways to make n cents. G(x) = Σ aₙxⁿ.

Pennies contribute: 1 + x + x² + ... = 1/(1-x) (use 0,1,2,... pennies).

Nickels contribute: 1 + x⁵ + x¹⁰ + ... = 1/(1-x⁵) (use 0,1,2,... nickels).

G(x) = 1/(1-x) × 1/(1-x⁵) = coefficient of xⁿ is the number of ways.

For n=10: ways = coefficients of x¹⁰ in 1/((1-x)(1-x⁵)). Enumerate: (0 nickels: 11 pennies... wait, 10 pennies: 1 way), (1 nickel, 5 pennies: 1 way), (2 nickels: 1 way). Total: 3 ways.

Answer

For n=10¢: 3 ways (10 pennies; 1 nickel + 5 pennies; 2 nickels). Generating function: G(x) = 1/((1-x)(1-x^5)).

Common Mistakes

!
Evaluating at x=1 to get the 'count' — but G(1) often diverges. Use G(1) only when the sequence is a probability distribution (then G(1) = 1 is the normalization check).
!
Not recognizing 1/(1-αx) as the geometric series generating function. Most rational generating functions decompose into partial fractions of this form.
!
Confusing OGF and EGF (exponential generating function). For labeled structures, use EGF = Σ aₙ xⁿ/n!. Compositions = OGF; permutations/labeled structures = EGF.

Practice Problems

Click "Show Answer" to reveal

Find a closed form for the number of ways to tile a 2×n board with 1×2 dominoes.

Hint: Let aₙ = number of tilings of a 2×n board. The last column is either covered by a vertical domino (leaves 2×(n-1)) or by two horizontal dominoes (leaves 2×(n-2)). Recurrence: aₙ = aₙ₋₁ + aₙ₋₂.

The number of ways to climb n stairs, taking 1 or 2 steps at a time, satisfies what recurrence? Solve for the closed form.

Hint: cₙ = cₙ₋₁ + cₙ₋₂ with c₁=1, c₂=2. This is a Fibonacci-type recurrence.

Back to Study Plan

Permutation Statistics: Records & Fixed Points Normal Distribution & CLT