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.

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

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