This is part 3 of our series on generating functions. Part 1 handled the quicksort recurrence. Part 2 used ordinary generating functions to count marbles in a can.

In this post we introduce exponential generating functions, which are what you reach for when the order of the objects you are counting matters. As with the earlier posts, our working notes live on the Generating Functions page of our wiki.

When Order Matters

The marbles-in-a-can problem from part 2 was order-independent. A can containing three reds, two blues, and one yellow is the same can no matter what order you put the marbles in. That is why ordinary generating functions worked - the coefficient of \(z^n\) just counted unordered combinations.

Now suppose we are counting ternary strings: sequences of digits from \(\{0, 1, 2\}\) of length \(n\). Here order matters. \(012\) and \(210\) are different strings, even though they use the same digits.

For problems like this we use exponential generating functions, defined using \(\tfrac{z^n}{n!}\) instead of \(z^n\). The base building block is \(e^z\) instead of \(\tfrac{1}{1-z}\):

The \(n!\) in the denominator is where the "order matters" bookkeeping happens automatically.

The Problem

Count the ternary strings of length \(n\) that contain an even number of 0s.

Setting Up

As with the marbles problem, we write one generating function per digit and multiply.

Digits 1 and 2 are unconstrained - any number can appear:

Digit 0 is where the constraint lives. We need an even number of them, which means we want the series

Here is a nice trick. Write out \(e^z\) and \(e^{-z}\):

Adding them, the odd terms cancel and the even terms double:

That is exactly the generating function we need for the 0s:

The \((e^z + e^{-z})/2\) trick is one of the most useful little identities in this whole business. If you ever need "only even terms" or "only odd terms", this is how you get them.

Multiplying

The overall generating function is

which is beautifully compact.

Extracting the Coefficient

Convert \(e^{3z}\) and \(e^{z}\) back to series:

The coefficient of \(\tfrac{z^n}{n!}\) is the number of ternary strings of length \(n\) with an even number of 0s:

Sanity Check

Length 1: \(\tfrac{3 + 1}{2} = 2\). The strings are "1" and "2" (both have zero 0s, and zero is even). ✓

Length 2: \(\tfrac{9 + 1}{2} = 5\). There are 9 total ternary strings of length 2. The ones with an even number of 0s are: 11, 12, 21, 22 (zero 0s), and 00 (two 0s). That is 5. ✓

Length 3: \(\tfrac{27 + 1}{2} = 14\). Out of 27 total, we want strings with 0 or 2 zeros. Strings with zero 0s use only {1, 2}, giving \(2^3 = 8\). Strings with two 0s have the two 0s in one of \(\binom{3}{2} = 3\) positions and a 1 or 2 in the remaining position, giving \(3 \cdot 2 = 6\). Total is \(8 + 6 = 14\). ✓

The Payoff

Ordinary generating functions counted the marbles problem, where order did not matter. Exponential generating functions handled the ternary-strings problem, where order did. In both cases the recipe is the same:

1. Write down a generating function per "slot" (per color, per digit).
2. Encode the constraints in the shape of the individual series.
3. Multiply.
4. Read off the coefficient.

The only real difference is whether you build out of \(z^n\) or \(\tfrac{z^n}{n!}\), and which little identities you have in your toolkit for shaping series to match constraints. The \((e^z + e^{-z})/2\) trick is one of the good ones.

References

• Our wiki notes: Generating Functions
• Trotter, Applied Combinatorics, Chapter 8 (exponential generating functions section)

This is part 2 of our series on generating functions. In part 1 we used generating functions to solve the quicksort recurrence, which is a serious industrial-strength application. This time we will use them for something a lot more whimsical: counting how many different cans of colored marbles you can put together under a bunch of arbitrary rules.

The example is from Trotter's Applied Combinatorics. Our working notes for this one, along with a few related exercises, live on the Generating Functions page of our wiki.

The Problem

We are packing cans of marbles. Each can holds 20 marbles, in some combination of red, blue, yellow, and green. The rules are:

• Each can must have at least one red marble.
• Each can can have no more than three blue marbles.
• Yellow marbles can appear in any quantity.
• Green marbles can only appear in multiples of 4.

How many different cans of 20 marbles are there?

The Generating Function Approach

The trick with problems like this is to write down one generating function per color, where the coefficient of \(z^k\) represents "the number of ways to put \(k\) marbles of this color in the can." Then multiply them all together. The coefficient of \(z^{20}\) in the product is the answer.

Each rule turns into a constraint on the shape of that color's series.

Red must have at least one, so the \(z^0\) term is missing:

Blue can have zero to three, and no more, so it is a polynomial:

Yellow is unconstrained:

Green appears only in multiples of 4. So the only nonzero coefficients are on \(z^0, z^4, z^8, \dots\):

(The substitution \(u = z^4\) turns this into the familiar \(\tfrac{1}{1-u}\), which is where the closed form comes from.)

Multiplying It All Together

The total generating function is

There is a nice simplification hiding in there. Notice that \(1 + z + z^2 + z^3 = \tfrac{1 - z^4}{1 - z}\), so the \(1 - z^4\) cancels with the denominator of \(G_g\), and the \(1 - z\) in the numerator eats one power of the \(\tfrac{1}{1-z}\) factors. What is left is

Which is much easier to work with.

Reading Off the Answer

We want the coefficient of \(z^{20}\) in \(\dfrac{z}{(1-z)^3}\).

The expansion of \(\dfrac{1}{(1-z)^3}\) is

which is the triangle-number sequence \(1, 3, 6, 10, 15, 21, \dots\).

Multiplying by \(z\) shifts the coefficients up by one power, so the coefficient of \(z^n\) in \(G(z)\) is \(\binom{n+1}{2}\).

For a can of 20 marbles:

So there are exactly 210 different cans of 20 marbles that satisfy all the rules.

The General Problem: How Do You Read Coefficients Off Anything?

The step above worked because we recognized \(\tfrac{1}{(1-z)^3}\) on sight. That is not the general case. In real problems you multiply four or five generating functions together, simplify, and end up staring at some expression like

and the question is: now what? How do you turn that back into a sequence, a closed form for \(a_n\), or at least something you can look up? This is the reverse direction of the whole generating-function program, and it deserves an explicit toolkit rather than a "you'll recognize it" hand-wave.

Here is the toolkit we actually reach for, in order of first resort. The first three steps are practical tools that will hand you an answer in seconds. The rest are the by-hand techniques that let you understand or manipulate what the tools give back.

1. Just ask Wolfram Alpha

This is the first tool to reach for. Full stop. Ahead of the algebra, ahead of the cheat sheet, ahead of everything. Type your generating function into Wolfram Alpha with a natural-language series request and it will hand you back the expansion:

series (1-z^4)/((2-4z^2)*(1-z)) to 50 terms

or

series expansion of z/(1-z)^3 at z=0 to order 22

You get the first N coefficients, immediately, with no setup, no notebook, no environment. Wolfram Alpha will also do partial fractions (partial fractions of ...), Taylor expansions, and single-coefficient extraction (coefficient of z^20 in ...) as one-line queries. If you want a closed form, sequence 1, 3, 6, 10, 15, 21 will often produce one, plus the generating function and recurrence.

The reason this matters more than it might sound: an enormous class of counting problems has generating functions that factor into a product of \(\tfrac{1}{1 - z^{c_i}}\) terms — one factor per denomination, coin type, box size, whatever the allowed "units" are in the problem. Polya's classic change for a dollar problem is exactly this shape:

The number of ways to make change for \(n\) cents is \([z^n] G(z)\). Doing partial fractions on that by hand is a slog and the closed form is ugly. Asking Wolfram Alpha series expansion of 1/((1-z)(1-z^5)(1-z^10)(1-z^25)(1-z^50)(1-z^100)) to 101 terms gives you the whole table in one shot, including the famous answer of 293 for \(n = 100\).

For anything in this family — restricted partitions, compositions with allowed part sizes, Frobenius / coin problems, our marble problem — this is a one-shot solution. Do not talk yourself out of using it. The by-hand techniques below are for when you want a closed form or an identity you can prove; if all you want is the number, Wolfram Alpha is done before you have finished writing the query.

2. Compute a few terms and look them up in OEIS

Once you have coefficients from step 1 (or by hand), if the sequence does not have an obvious closed form, type the integers into the Online Encyclopedia of Integer Sequences.

OEIS will tell you the sequence's name, closed-form expression if one exists, recurrence, generating function, and every combinatorial interpretation anyone has ever noticed. If your sequence starts \(1, 1, 2, 5, 14, 42, \dots\), OEIS hands you back "Catalan numbers" and a page of context. If it starts \(1, 3, 11, 50, 274, \dots\) you learn it is A000670, the Fubini numbers, counting ordered set partitions — a connection you would probably not have made from the generating function alone.

The Wolfram Alpha → OEIS pipeline is the single most powerful move in this whole toolkit. Half the sequences that come up in combinatorics have names, and knowing the name gives you access to identities and asymptotics that would take you weeks to rederive.

3. Drop into a computer algebra system

When you want to keep the result in a script, do further manipulation, or extract many coefficients programmatically, use sympy or Mathematica. In sympy:

from sympy import symbols, series, apart
z = symbols('z')
G = z / (1 - z)**3
series(G, z, 0, 22)          # expand as a power series
apart(G, z)                  # partial fraction decomposition
G.series(z, 0, 22).coeff(z, 20)   # coefficient of z^20

Wolfram Alpha handles one-off queries in the browser; sympy is what you reach for when the generating function is being constructed programmatically or the coefficients feed into further computation.

The three tools above will get you a number — often the number you wanted. The next four techniques are for the case where you want more than a number: a closed form, a proof, or an understanding of why the sequence looks the way it does.

4. Match against a table of standard series

The single most productive by-hand move is to keep a cheat sheet of standard generating functions and their coefficients. If you can massage your expression into a sum of these, you have a closed form.

The core list:

The third one, the negative binomial series, is the workhorse. Almost every rational generating function with only \((1-z)^k\)-style denominators reduces to a sum of these, and their coefficients are binomial coefficients in \(n\).

5. Partial fractions to break the expression apart

If your expression is a rational function \(\tfrac{P(z)}{Q(z)}\) where \(Q(z)\) factors into simple pieces like \((1 - a_i z)^{k_i}\), expand it by partial fractions:

Each piece is a standard series from step 4. Reading coefficients off the sum is then just adding standard-series coefficients term by term. This is how you get closed forms with mixed geometric and polynomial behavior, like \(a_n = A \cdot a_1^n + (B + C n) \cdot a_2^n\).

For the Fibonacci generating function \(\tfrac{z}{1 - z - z^2}\), this exact procedure produces Binet's formula. It is a very general hammer.

6. Use the calculus of generating functions

A handful of operations on a generating function correspond to clean operations on its coefficient sequence. Recognizing them lets you build up unfamiliar expressions from familiar ones.

• Multiplying by \(z\) shifts coefficients: if \(A(z) = \sum a_n z^n\) then \(z \cdot A(z) = \sum a_{n-1} z^n\). This is what we used above to get from \(\binom{n+2}{2}\) to \(\binom{n+1}{2}\).
• Differentiating produces \(A'(z) = \sum n \, a_n \, z^{n-1}\), and multiplying that by \(z\) gives \(\sum n \, a_n \, z^n\). So the "times \(n\)" operator on a sequence is \(z \tfrac{d}{dz}\) on the generating function. This is how you get things like \(\sum n z^n\) from \(\sum z^n\).
• Integrating goes the other way: dividing coefficients by \(n\).
• Multiplying two generating functions convolves their coefficient sequences: \(\sum_{k=0}^{n} a_k \, b_{n-k}\). Sometimes you will recognize a convolution in a combinatorial identity you are trying to prove.
• Substituting \(z \to z^m\) spreads coefficients out, putting zeros between them. Substituting \(z \to a z\) multiplies coefficient \(n\) by \(a^n\).

If you see a generating function that looks like a standard one with an extra factor of \(z\) or an extra power of \(n\) in front, these operations are usually how it got there — and they tell you how to undo it.

7. Extract a single coefficient directly

Sometimes you do not need the whole sequence, just one term. The formal notation is

and there are algebraic rules for pushing \([z^n]\) around:

For rational \(A(z)\) with small denominators, you can also just do long division of the series until you reach the \(z^n\) term. Tedious but mechanical, and useful for a sanity check against Wolfram Alpha.

8. When nothing closes: asymptotics

Some generating functions simply do not have a nice closed-form coefficient. That is fine. In those cases you switch questions: instead of "what is \(a_n\) exactly?" you ask "how does \(a_n\) grow with \(n\)?" The answer usually falls out of the location and type of the singularities of \(A(z)\) nearest the origin — this is singularity analysis, and Flajolet and Sedgewick's Analytic Combinatorics is the reference. It is out of scope for this series, but worth knowing exists: even when you cannot read off an answer, you can often read off the growth rate.

Applied to our expression

For \(\tfrac{z}{(1-z)^3}\) we used step 4 (recognize a standard series) and step 6 (multiply by \(z\) shifts the index). Two lines of algebra and a closed form falls out. But we could just as easily have typed series z/(1-z)^3 to 22 terms into Wolfram Alpha, read off 210 as the coefficient of \(z^{20}\), dropped \(1, 3, 6, 10, 15, 21\) into OEIS, and learned that these are triangle numbers with generating function \(\tfrac{z}{(1-z)^3}\) and closed form \(\binom{n+1}{2}\) — arriving at the same place from the other direction.

Both directions are legitimate. Which one you use depends on whether you want the answer or the understanding. Usually you want both, which means using the tools to get the answer fast and then doing the algebra to see why.

Sanity Check on Small Cases

We can verify the closed form by walking through small \(n\).

\(n = 1\) (one marble): Only one configuration works - the single red marble. Coefficient is \(\binom{2}{2} = 1\). ✓

\(n = 2\) (two marbles): One slot is red. The other slot can be red, blue, or yellow (green is out because it only appears in multiples of 4). That is 3 configurations: RR, RB, RY. Coefficient is \(\binom{3}{2} = 3\). ✓

\(n = 3\) (three marbles): Same idea, one is red, the other two are drawn from {R, B, Y}. Enumerating: RRR, RRB, RRY, RBB, RBY, RYY. That is 6. Coefficient is \(\binom{4}{2} = 6\). ✓

The pattern of \(3, 6, 10, 15, \dots\) is a run of triangle numbers, which is exactly what \(\binom{n+1}{2}\) produces.

The Point

You could solve this problem by writing a script that enumerates every combination of \((r, b, y, g)\) with \(r+b+y+g = 20\) and the constraints respected, and it would work fine. The generating function approach does something different: it gives you a closed form for the answer as a function of \(n\). Change the can size to 50, and you get \(\binom{51}{2} = 1275\) without running anything.

Also, and this matters more than it sounds: turning "no more than three" into a polynomial and "multiples of four" into a series in \(z^4\) takes the constraints out of your enumeration logic and puts them into algebra. Algebra is easier to check than nested loops.

Next in the series: what happens when order matters, and we need to switch from ordinary generating functions to exponential generating functions.

References

• Our wiki notes: Generating Functions
• Trotter, Applied Combinatorics, Chapter 8
• Flajolet and Sedgewick, Analytic Combinatorics — for singularity analysis and asymptotics

This post is part 1 of a series on generating functions, based on notes we have been working through from Sedgewick and Flajolet's Analysis of Algorithms and Trotter's Applied Combinatorics. The full set of notes lives on our wiki: Generating Functions.

Generating functions are one of those techniques that look completely mysterious the first time you see them, and then look like the obvious thing to do the tenth time you see them. They turn recurrences into functions, functions into series, and series back into closed forms for the coefficients you actually wanted. This post walks through one of the nicest applications: solving the recurrence relation for quicksort.

The Recurrence

The average number of comparisons quicksort makes on an array of size \(n\) satisfies the recurrence

The \(n+1\) term is the cost of the partition step. The sum averages the cost of recursing on the two subarrays over all possible choices of pivot.

Staring at that sum inside the recurrence is not a great starting point. Everything on the right depends on every \(C_k\) that came before. Generating functions are how we get out.

Setting Up the Generating Function

The plan is to introduce a generating function

and then translate each piece of the recurrence into an operation on \(C(z)\).

Multiplying the recurrence by \(n\) to clear the \(\tfrac{2}{n}\), and then by \(z^n\), and summing over \(n\), we end up with

Each of these three terms turns into something in \(C(z)\):

• The left side is \(z C'(z)\), since taking a derivative and multiplying by \(z\) pulls out an \(n\) from each term of the series
• The first term on the right involves the second derivative of \(\tfrac{1}{1-z}\), and simplifies to \(\tfrac{2}{(1-z)^3}\)
• The double sum is a partial-sum operation, which corresponds to multiplying by \(\tfrac{1}{1-z}\)

Putting it all together, we get

The recurrence has become a first-order linear differential equation.

Solving the ODE

To solve

we look for an integrating factor \(\rho(z)\) such that \(\rho'(z) = -\dfrac{2 \rho(z)}{1-z}\). That works out to \(\rho(z) = (1-z)^2\).

Multiplying through:

Integrating both sides:

And so

That is the generating function for the average number of comparisons in quicksort. Not obvious.

Reading Off the Coefficient

Now we extract \(C_n = [z^n] C(z)\). The expression \(\tfrac{1}{(1-z)^2}\) has the well-known expansion \(\sum (n+1) z^n\), and \(\ln \left( \tfrac{1}{1-z} \right)\) has the expansion \(\sum \tfrac{z^k}{k}\), which is the generating function for the sequence \(H_k = 1 + \tfrac{1}{2} + \dots + \tfrac{1}{k}\) (the harmonic numbers, once you divide by \(\tfrac{1}{1-z}\) to accumulate).

Working through the convolution, we land at

That is the closed form. Since \(H_n \approx \ln n + \gamma\) for large \(n\), this gives \(C_n \sim 2 n \ln n\), which recovers the familiar \(O(n \log n)\) average case for quicksort - with an actual constant in front of it.

Why This Is Worth Learning

The reason this technique is so satisfying is that we started with a recurrence that looked completely intractable - \(C_n\) depends on the entire prefix \(C_0, C_1, \dots, C_{n-1}\) - and ended with a clean closed form.

The mechanical steps are:

1. Turn the recurrence into a functional equation in \(C(z)\) by multiplying by \(z^n\) and summing.
2. Solve the functional equation. Sometimes it is algebraic, sometimes it is a differential equation (as here).
3. Extract the \(n\)-th coefficient of the solution.

In upcoming posts in this series, we will look at simpler examples that show how the coefficient extraction step works, including a nice puzzle about distributing colored marbles into cans with weird constraints.

References

• Our full notes: Generating Functions on the wiki (Sedgewick/Flajolet and Trotter, side by side)
• Knuth-flavored coverage: AOCP/Generating Functions