Generating Functions in Combinatorics

Some counting questions resist direct reasoning. "How many ways can I make change for a dollar using pennies, nickels, dimes, and quarters?" You could enumerate cases for hours and still miss one. Generating functions solve an entire family of such problems by converting "count the ways" into "multiply out some algebra and read off a coefficient" — turning combinatorics into arithmetic a computer, or a patient human, can just grind through.

The analogy: a sequence hiding inside a polynomial

Think of a vending machine slot that can hold $0$, $1$, or $2$ of an item. Write that as the polynomial $1 + x + x^2$ — the exponent of $x$ is "how many you took," and every exponent that's allowed gets a coefficient of 1 (the "1" out front of each term means "one way to take that many").

Now suppose you have two such slots and want to know, for each total count, how many ways to reach it. Multiply the polynomials:

$$(1 + x + x^2)(1 + x + x^2) = 1 + 2x + 3x^2 + 2x^3 + x^4.$$

Read off the coefficients: 1 way to take 0 total, 2 ways to take 1 total (from either slot), 3 ways to take 2 total, and so on. You never listed a single case — ordinary polynomial multiplication did the counting for you, because multiplying polynomials automatically adds up every pair of exponents, which is exactly what "combine choices from two sources" means.

Writing it down

A generating function for a sequence $a_0, a_1, a_2, \ldots$ is the (formal — we never actually plug in a number) power series

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

In words: $x$ is just a bookkeeping symbol whose exponent tracks "which term," and the coefficient sitting on $x^n$ is the answer to your counting question for size $n$. You don't care what $G(x)$ "equals" as a number — you care about extracting $a_n$, written $[x^n]\,G(x)$ ("the coefficient of $x^n$ in $G(x)$").

The single most useful building block is the geometric series:

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

In words: an item you can take any number of times (0, 1, 2, …), each in exactly one way, is encoded by $\frac{1}{1-x}$. This closed form is the whole payoff of the method — instead of an infinite sum you carry around one small fraction, and multiplying several such fractions together (one per type of item) still just multiplies out to another closed form you can expand.

Drag the exponent in the explorer above and watch how a power series' shape changes — it's the same object living on the other side of the equals sign: $\frac{1}{1-x}$ is the compressed, closed-form twin of the infinite sum $1+x+x^2+\cdots$, and generating-function algebra works by manipulating the compressed form and only expanding back out at the very end, when you need one specific coefficient.

Worked example 1: making change, four coin types

Back to the vending-machine question, done properly. Using $p$ pennies (worth 1c, unlimited), $n$ nickels (5c), $d$ dimes (10c), and $q$ quarters (25c), how many ways to make exactly 10 cents?

Each coin type, used any number of times, contributes a geometric-series factor — but in the value it contributes, so pennies track $x^1$ per coin, nickels $x^5$ per coin, and so on:

$$G(x) = \underbrace{\frac{1}{1-x}}_{\text{pennies}} \cdot \underbrace{\frac{1}{1-x^5}}_{\text{nickels}} \cdot \underbrace{\frac{1}{1-x^{10}}}_{\text{dimes}} \cdot \underbrace{\frac{1}{1-x^{25}}}_{\text{quarters}}.$$

We want $[x^{10}]\,G(x)$. Rather than expand the whole product, restrict to terms that can reach exponent 10: pennies contribute $1, x, x^2, \ldots$ up to $x^{10}$; nickels contribute $1, x^5, x^{10}$; dimes contribute $1, x^{10}$; quarters contribute only $1$ (since $x^{25}$ already overshoots). Enumerate the coin-count combinations that sum to 10 cents directly, now organized by this factorization: 0 dimes and 0 nickels → 10 pennies (1 way); 0 dimes, 1 nickel → 5 pennies (1 way); 0 dimes, 2 nickels → 0 pennies (1 way); 1 dime, 0 nickels → 0 pennies (1 way). Total: 4 ways. The generating function didn't shortcut the arithmetic here — with only 10 cents the direct count is just as fast — but the same four fractions, multiplied out by a computer algebra system, answer "how many ways to make $47.32" exactly as easily, which is where hand enumeration would never finish.

Worked example 2: Fibonacci from a generating function

The Fibonacci sequence $F_0=0, F_1=1, F_n = F_{n-1}+F_{n-2}$ counts, among other things, the number of ways to tile a $1\times n$ strip with $1\times1$ and $1\times2$ tiles. Find a closed form for $F_n$.

Let $G(x) = \sum F_n x^n$. Multiply the recurrence relation itself by $x^n$ and sum over $n \ge 2$:

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

The left side is $G(x) - F_0 - F_1x = G(x) - x$. The right side's sums are $x\,G(x)$ and $x^2 G(x)$. So $G(x) - x = xG(x) + x^2 G(x)$, and solving for $G(x)$:

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

In words: the entire infinite Fibonacci sequence is compressed into one fraction. To get a formula for $F_n$ itself, factor the denominator using the roots of $t^2 - t - 1=0$, which are $\varphi = \frac{1+\sqrt5}{2}$ (the golden ratio) and $\psi = \frac{1-\sqrt5}{2}$. Partial-fraction decomposition and expanding each piece as a geometric series gives Binet's formula:

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.$$

Check it: $F_{10}$ should be 55. $\varphi \approx 1.618$, so $\varphi^{10}\approx 122.99$; $\psi\approx-0.618$, so $\psi^{10}\approx0.0081$. $(122.99 - 0.008)/\sqrt5 \approx 122.98/2.236 \approx 55.0$. Matches — and now you can compute $F_{100}$ directly, with no recursion and no 100-step loop.

What this means in practice

• Counting paths and states. Anywhere you count "number of sequences/paths satisfying a constraint" — coin change, dice-sum distributions, lattice paths — a product of simple factors like $\frac{1}{1-x^k}$ usually encodes the whole problem.
• Solving recurrences. Any linear recurrence (Fibonacci-style trading signals, cash-flow recursions, difference equations in a discretized PDE) can be solved in closed form this way instead of simulated step by step.
• Probability generating functions. The same object with $x^n$ replaced by probability weights (moment generating functions, characteristic functions) is how sums of independent random variables get analyzed — convolution of distributions becomes multiplication of generating functions, exactly as in the change-making example.
• Interview problems. "How many ways to roll a sum of $S$ with $k$ dice" or "how many binary strings avoid three consecutive 1s" are textbook generating-function setups once you recognize the pattern.