Generating Functions

A generating function is one of the strangest and most powerful ideas in combinatorics: you take a whole sequence of numbers a_0, a_1, a_2, \dots and hang them on the powers of a formal variable, making a single power series:

A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n.

The variable x is just a bookkeeping peg — you rarely plug a number into it. As the mathematician Herbert Wilf put it, "a generating function is a clothesline on which we hang up a sequence of numbers for display." The magic is that operations on sequences become algebra on functions: shifting, summing, and — best of all — convolving sequences turn into multiplying, dividing, and manipulating tidy closed-form expressions. A hard recurrence becomes a routine bit of algebra, and the answer falls out as a coefficient.

The one generating function to know

Everything is built on the geometric series. The sequence of all 1's, (1, 1, 1, \dots), has generating function

1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}.

As a function this only converges for |x| < 1 — the chart below shows the truncated polynomial creeping up onto the curve 1/(1-x) as you add terms — but as a formal generating function we never care: the identity is an exact statement about coefficients. From this one fact, differentiation and substitution spin off a whole toolkit:

\dfrac{1}{1-x} = \sum_{n\ge0} x^n — coefficients all 1.
\dfrac{1}{1-cx} = \sum_{n\ge0} c^n x^n — coefficients c^n (geometric).
\dfrac{1}{(1-x)^2} = \sum_{n\ge0} (n+1)\,x^n — coefficients n+1 (differentiate the first).
\dfrac{1}{(1-x)^k} = \sum_{n\ge0} \binom{n+k-1}{k-1} x^n — the stars-and-bars counts.
(1+x)^m = \sum_{n} \binom{m}{n} x^n — the binomial theorem, read as a generating function for \binom{m}{n}.

Why multiplication counts: the convolution

The single most important move is that multiplying generating functions convolves the sequences. If A(x) = \sum a_i x^i and B(x) = \sum b_j x^j, then the coefficient of x^n in the product is

[x^n]\,A(x)B(x) = \sum_{i+j=n} a_i\, b_j.

That sum is exactly what the product rule produces when you combine a size-i piece with a size-j piece to build something of total size n. So "choose some of these and some of those, totalling n" — a counting problem — is a coefficient of a product. Squaring \frac{1}{1-x} gives \frac{1}{(1-x)^2} whose x^n coefficient is \sum_{i+j=n} 1 \cdot 1 = n+1 — the number of ways to write n as an ordered sum of two non-negative integers. Counting has become coefficient-extraction.

The killer application: solving a recurrence

Generating functions turn recurrences into algebra. Take Fibonacci, F_n = F_{n-1} + F_{n-2} with F_0 = 0, F_1 = 1, and let F(x) = \sum_{n\ge0} F_n x^n. Multiply the recurrence by x^n and sum over n \ge 2; each shifted sum is a multiple of F(x):

F(x) - x = x\big(F(x)\big) + x^2 F(x) \;\Longrightarrow\; F(x) = \frac{x}{1 - x - x^2}.

The entire infinite sequence is packed into one tidy rational function. Split it by partial fractions over the roots of 1 - x - x^2 (the reciprocals of the golden ratio and its conjugate) and each piece is a geometric series \frac{1}{1-\varphi x}-style — reading off the coefficient hands you Binet's closed form F_n = \frac{\varphi^n - \psi^n}{\sqrt5} with no guessing at all. The same recipe — form the generating function, solve for it algebraically, expand — cracks any linear recurrence, and many nonlinear ones besides.

How many ways can you make n pence from 1p, 2p and 5p coins? Each coin type is a menu of "use 0, or 1, or 2, … of them", which as a generating function is 1 + x^{d} + x^{2d} + \cdots = \frac{1}{1 - x^{d}} for a coin of value d. Choosing amounts of each coin independently multiplies the menus, so the number of ways to make change is

[x^n]\ \frac{1}{(1 - x)(1 - x^2)(1 - x^5)}.

A physical counting problem — piles of coins — has become a single coefficient of a product of three simple series. This is the generating-function philosophy in one image: build the structure out of independent choices, and the algebra counts them for you.

Convergence is optional. A formal power series is a bookkeeping device; identities like \frac{1}{1-x} = \sum x^n hold as statements about coefficients even where the series would diverge. Don't refuse to use a generating function because "it only converges for |x|<1" — you are almost never substituting a number.
Mind the shift bookkeeping. When you multiply a recurrence by x^n and sum, the low-order terms (here the lone x from F_1) need separate care — dropping them gives the wrong rational function.
Ordinary vs exponential. This page uses ordinary generating functions (\sum a_n x^n), which count unlabelled structures. Labelled problems (permutations, set partitions) want exponential generating functions \sum a_n \frac{x^n}{n!} instead — using the wrong flavour miscounts by factorials.