Generating Functions

A generating function is simply a way to store a whole infinite sequence as one expression, by using the sequence's numbers as the coefficients of a power series. It's called that because expanding the function generates the sequence, term by term. All we're really doing is using a polynomial as a filing cabinet: the number in drawer $n$ is written as the coefficient of $x^n$. The formulas look scary, but $\frac{1}{1 - x} = 1 + x + x^2 + \cdots$ is just the geometric series from earlier in this unit (every drawer holds a 1), and the second formula says what's in drawer $n$ when you multiply $k$ of those together ($n$ is the drawer number, $k$ is how many factors). The variable $x$ never gets a value; it's only a label. Bear with it, because once you see why multiplying works, the rest is bookkeeping.

The sequence $1, 1, 1, \dots$ has generating function $1 + x + x^2 + \cdots = \frac{1}{1 - x}$, and $1, 2, 4, 8, \dots$ has $\frac{1}{1 - 2x}$, by the same geometric series with $2x$ in place of $x$.

Multiplication combines choices. Think about what happens when you multiply out $A(x)B(x)$. You get an $x^n$ term every time you pick $x^i$ from the first factor and $x^j$ from the second with $i + j = n$, so the coefficient of $x^n$ adds up $a_ib_j$ over all those splits. That's exactly the count of ways to split $n$ between two independent choices. So the number of ways to make $n$ cents from pennies and nickels is the coefficient of $x^n$ in

The first factor says "any number of cents from pennies," the second says "a multiple of 5 cents from nickels," and multiplying them lets the exponents add up.

Multiplying $k$ copies of $\frac{1}{1 - x}$ counts ways to split $n$ among $k$ types, and we get back stars and bars: the coefficient is $\binom{n + k - 1}{k - 1}$.

Recurrences become algebra. The Fibonacci recurrence turns into $F(x) = x + xF(x) + x^2F(x)$, so $F(x) = \frac{x}{1 - x - x^2}$, and partial fractions give Binet's formula again. It's a second road to the answer from the last lesson.

A common mistake. It's tempting to worry about whether $1 + x + x^2 + \cdots$ "equals" $\frac{1}{1 - x}$ when, say, $x = 2$, since the series obviously blows up there. For counting it doesn't matter. These series are treated formally: we only care about the coefficients and never plug in numbers. (Inside $|x| < 1$ the series really do converge to the functions, which is a nice bonus, not a requirement.)

Probability theory, queueing models and the analysis of algorithms all count with generating functions.