Helpful context:

Imagine you have a sequence of numbers - say, the number of ways to make change for $n$ cents - and you want to understand it. You could compute the first few terms, look for a pattern, maybe guess a formula. Or you could encode the entire sequence as a single algebraic object: a power series whose coefficients are exactly the terms you care about. This might sound like it adds complexity, but it turns out that questions about the sequence translate into algebraic questions about the series, and algebra is often easier than combinatorics.

This is the generating function philosophy, articulated most vividly by Herbert Wilf in his classic book generatingfunctionology: “A generating function is a clothesline on which we hang up a sequence of numbers for display.” The series itself is treated as a formal object - we do not ask whether it converges, because we are doing algebra, not analysis. The power of the method comes from the fact that algebraic manipulations on the generating function correspond to natural operations on the sequence: multiplying two generating functions convolves their coefficient sequences, differentiating brings down factors of $n$, and shifting multiplies by $x$.

The method has two complementary modes. In the analytical mode, you write down the generating function for a known sequence (like geometric series for $\{1, 1, 1, \ldots\}$), combine functions to reflect combinatorial constraints (like picking coins of different denominations), and then extract coefficients using algebra. In the recursive mode, you translate a recurrence on the sequence into a functional equation for the generating function, solve the equation, and recover the sequence via series expansion. Both modes are indispensable, and mastering generating functions means being fluent in both.

Formal Power Series

An ordinary generating function (OGF) for a sequence $a_0, a_1, a_2, \ldots$ is the formal power series

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

We write $[x^n] A(x) = a_n$ for the operation of extracting the coefficient of $x^n$.

The word “formal” means we treat $x$ as an indeterminate - we add and multiply these series using the usual algebraic rules, without worrying about convergence. Addition is termwise: $[x^n](A(x) + B(x)) = a_n + b_n$. Multiplication is convolution: $[x^n](A(x) \cdot B(x)) = \sum_{k=0}^n a_k b_{n-k}$.

A few foundational series to know by heart:

$$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n \quad \text{(geometric series, all-ones sequence)}$$

$$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1) x^n \quad \text{(sequence of } n+1\text{)}$$

$$\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n \quad \text{(stars and bars)}$$

$$(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k \quad \text{(binomial coefficients)}$$

Basic Operations on Generating Functions

The real power comes from how operations on $A(x)$ translate to operations on $(a_n)$:

Shift right. $x A(x) = \sum_{n=1}^{\infty} a_{n-1} x^n$, i.e., $[x^n] x A(x) = a_{n-1}$. Multiplying by $x$ shifts the sequence right by one position (prepends a 0).

Shift left. $(A(x) - a_0)/x = \sum_{n=0}^{\infty} a_{n+1} x^n$, i.e., $[x^n] (A(x)-a_0)/x = a_{n+1}$.

Differentiation. $A'(x) = \sum_{n=1}^{\infty} n a_n x^{n-1}$, so $[x^n] A'(x) = (n+1) a_{n+1}$. Equivalently, $[x^n] x A'(x) = n a_n$.

Convolution. If $A(x)$ encodes $(a_n)$ and $B(x)$ encodes $(b_n)$, then $A(x)B(x)$ encodes the sequence whose $n$-th term is $\sum_{k=0}^n a_k b_{n-k}$. This is the fundamental identity: multiplying generating functions corresponds to convolving their coefficient sequences.

Solving Fibonacci

The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$.

Let $F(x) = \sum_{n=0}^{\infty} F_n x^n$. Multiply the recurrence by $x^n$ and sum over $n \geq 2$:

$$\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n.$$

The left side is $F(x) - F_1 x - F_0 = F(x) - x$. The right side:

$$x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} = x(F(x) - F_0) = xF(x),$$

$$x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x^2 F(x).$$

So $F(x) - x = xF(x) + x^2 F(x)$, giving

$$F(x)(1 - x - x^2) = x \implies F(x) = \frac{x}{1 - x - x^2}.$$

To extract coefficients, factor the denominator. The roots of $1 - x - x^2 = 0$ are $x = \frac{-1 \pm \sqrt{5}}{2}$. Let $\phi = \frac{1+\sqrt{5}}{2}$ (the golden ratio) and $\psi = \frac{1-\sqrt{5}}{2}$. Then $1 - x - x^2 = -(x - 1/\phi)(x - 1/\psi) \cdot (-1)$… more cleanly, partial fractions give

$$F(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \phi x} - \frac{1}{1 - \psi x}\right).$$

Each term is a geometric series: $\frac{1}{1 - \phi x} = \sum_{n=0}^{\infty} \phi^n x^n$. Extracting coefficients:

$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$

This is Binet’s formula. The generating function approach derives it purely by algebra, without guessing the form of the solution.

Counting with Generating Functions: Making Change

How many ways can you make change for $n$ cents using pennies (1 cent), nickels (5 cents), and dimes (10 cents)?

Model each coin type independently. The number of ways to use $k$ pennies is 1 for every $k \geq 0$ (you use exactly $k$ pennies), contributing a factor of

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

Similarly, nickels (denomination 5) contribute $\frac{1}{1-x^5}$ and dimes contribute $\frac{1}{1-x^{10}}$.

The total generating function is

$$\frac{1}{(1-x)(1-x^5)(1-x^{10})}.$$

The coefficient $[x^n]$ in this series is exactly the number of ways to make change for $n$ cents. No counting argument is needed - the algebra encodes the combinatorics automatically. This generalizes immediately: for any set of coin denominations $\{d_1, d_2, \ldots, d_k\}$, the generating function is $\prod_{i=1}^k \frac{1}{1 - x^{d_i}}$.

Solving the Catalan Recurrence

The Catalan numbers satisfy $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$. In terms of the generating function $C(x) = \sum C_n x^n$:

The right side of the recurrence is a convolution: $\sum_{i=0}^{n-1} C_i C_{n-1-i} = [x^{n-1}] C(x)^2$.

Multiplying through: $C_n = [x^{n-1}] C(x)^2$, so $C(x) - C_0 = x C(x)^2$, i.e.,

$$C(x) = 1 + x C(x)^2.$$

Solving this quadratic in $C(x)$:

$$x C(x)^2 - C(x) + 1 = 0 \implies C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

(taking the minus sign so that $C(0) = C_0 = 1$, which can be verified by L’Hôpital or by the binomial expansion). Expanding via the generalized binomial series recovers $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Exponential Generating Functions

For sequences that count labeled structures, the ordinary generating function is often the wrong tool. Instead, use the exponential generating function (EGF):

$$\hat{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}.$$

The division by $n!$ accounts for the redundancy when combining labeled structures. The key identity: if $\hat{A}(x)$ encodes a sequence of labeled structures of type $A$ and $\hat{B}(x)$ encodes type $B$, then $\hat{A}(x) \cdot \hat{B}(x)$ encodes the labeled structures formed by partitioning $n$ labels into two parts and placing an $A$-structure on one part and a $B$-structure on the other.

Permutations. There are $n!$ permutations of $n$ elements, so the EGF is

$$\sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}.$$

Derangements. A derangement of $n$ elements has no fixed points. The count is $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$. The EGF of derangements is

$$\hat{D}(x) = \sum_{n=0}^{\infty} D_n \frac{x^n}{n!} = \frac{e^{-x}}{1-x}.$$

This can be derived by noting that a permutation either fixes no element (derangement) or fixes some elements and deranges the rest, giving $\hat{D}(x) = e^{-x} / (1-x)$.

Set partitions and Bell numbers. Let $B_n$ be the number of ways to partition a set of $n$ elements into non-empty subsets (the $n$-th Bell number). Then $B_0=1, B_1=1, B_2=2, B_3=5, \ldots$ The EGF is

$$\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}.$$

This beautiful formula comes from the fact that a set partition is an unordered collection of non-empty subsets, and the EGF of non-empty sets is $e^x - 1$.

Rational Generating Functions and Linear Recurrences

Theorem. A sequence $(a_n)$ satisfies a linear recurrence with constant coefficients

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$

if and only if its generating function $A(x)$ is a rational function $P(x)/Q(x)$ where $\deg P < \deg Q = k$.

Proof sketch. The recurrence gives $a_n - c_1 a_{n-1} - \cdots - c_k a_{n-k} = 0$ for $n \geq k$. Multiplying by $x^n$ and summing: $A(x) Q(x) = P(x)$ where $Q(x) = 1 - c_1 x - \cdots - c_k x^k$ (the characteristic polynomial, reversed) and $P(x)$ encodes the initial conditions. Thus $A(x) = P(x)/Q(x)$.

Conversely, any rational function with denominator of degree $k$ has a partial fraction expansion in terms of $1/(1 - r_i x)^{m_i}$ where $r_i$ are the reciprocal roots and $m_i$ are their multiplicities. Each such term contributes a polynomial-times-exponential term to $a_n$.

The denominator $Q(x)$ is the key object: its reciprocal roots $r_i$ determine the exponential growth rates, and the multiplicities $m_i$ determine the polynomial prefactors.

The Wilf Philosophy

Herbert Wilf’s advice for combinatorial problems can be summarized as:

  1. Identify what you are counting. Define the sequence $(a_n)$ precisely.
  2. Write down the generating function. Even if you don’t know what $A(x)$ is explicitly, give it a name and write equations it satisfies.
  3. Do algebra. Manipulate $A(x)$ using the operations described above until you have a formula.
  4. Extract coefficients. Use partial fractions, Taylor series, or the binomial theorem.

Step 2 is where most of the combinatorial insight is needed - writing a functional equation for $A(x)$ requires understanding the recursive structure of what you are counting. Steps 3 and 4 are mechanical. This separation is what makes generating functions powerful: the combinatorics is concentrated in one equation, and the rest is algebra.

Summary

Operation on $A(x)$ Effect on $(a_n)$
$A(x) + B(x)$ $a_n + b_n$ (termwise sum)
$A(x) \cdot B(x)$ $\sum_{k=0}^n a_k b_{n-k}$ (convolution)
$x \cdot A(x)$ shift right: $[x^n] = a_{n-1}$
$A'(x)$ $[x^n] A'(x) = (n+1)a_{n+1}$
$xA'(x)$ $[x^n] = n \cdot a_n$
$A(x) = P(x)/Q(x)$ rational $(a_n)$ satisfies a linear recurrence
Sequence OGF
$\{1, 1, 1, \ldots\}$ $\frac{1}{1-x}$
$\{1, c, c^2, \ldots\}$ $\frac{1}{1-cx}$
$F_n$ (Fibonacci) $\frac{x}{1-x-x^2}$
$C_n$ (Catalan) $\frac{1-\sqrt{1-4x}}{2x}$

Read next: