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 …

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 …

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 …