Why is the derivative of a generating function meaningful?

A generating function is a formal power series where the sequence of coefficients is the object of interest. Usually the point of using them is that operations on the power series (like addition, multiplication, and differentiation) correspond to meaningful operations on your sequence of coefficients.

I’ve known about the gist of generating functions for a while, and I’d always thought that the fact that differentiation was meaningful was just a magical coincidence (for some reason, addition and multiplication being meaningful didn’t seem as surprising to me).

But recently, Nathan Linger pointed out to me that over in the functional programming community, they have what I think is a very satisfying answer to this question (he said he got it from sigfpe’s blog, but I’m not sure what post, maybe this one?).

Combinatorial Species

I actually find the general concept of generating functions surprisingly slippery.  André Joyal’s notion of a combinatorial species makes things more concrete for me.  A combinatorial species \mathbf{F} is simply a functor from \mathbb{B} to itself, where \mathbb{B} is the category of finite sets and bijections.  The idea is that, for a finite set S, \mathbf{F}(S) should be considered as the set of all structures of a certain kind on S.

For example: \mathbf{LinearOrder} is the functor taking a set S to the set of all linear orders of elements of S, so \mathbf{LinearOrder}(\{1, 2, 3\}) = \{1 < 2 < 3, 1 < 3 < 2, 2 < 1 < 3, 2 < 3 < 1, 3 < 1 < 2, 3 < 2 < 1\}.  Another example is \mathbf{Tree} which takes S to the set of all trees on elements of S.

Each species \mathbf{F} has an associated generating function F(x)=a_0 + a_1 x + \frac{a_2}{2!} x^2 + \frac{a_3}{3!} x^3 \ldots where a_i = |\mathbf{F}(\{1, \ldots, i\})| (you could use any set of cardinality i instead of \{1, \ldots, i\}.

It is now possible to make precise the fact that meaningful operations on species correspond to meaningful operations on generating functions.  For example, if you define addition on species by letting (\mathbf{F}+\mathbf{G})(S) be the disjoint union of \mathbf{F}(S) and \mathbf{G}(S), then the generating function of the sum of two species is the sum of the generating functions.  Similarly, multiplication on species is defined by letting (\mathbf{F}\cdot\mathbf{G})(S) be a pair of an element of \mathbf{F}(S_1) and an element of \mathbf{G}(S2) for some partition S1\sqcup S2=S, and it corresponds to multiplication of generating functions.

As mentioned before, there’s also an operation on species which corresponds to differentiation of the generating function.  It corresponds to an addition of a “hole” in the structure.  That is, \mathbf{F}'(S) = \mathbf{F}(S\sqcup\{\star\}), and \mathbf{F}' takes bijections on S to the output of \mathbf{F} on the same bijection but fixing \star.

This is a very powerful fact.  For example, a linear order with a hole is the same thing as the product of two linear orders (the one to the left of the hole and the one to the right of the hole).  If F is the generating function of \mathbf{LinearOrder}, this gives us the equation F' = F^2.  Since we also know that a_0 should be 1, this gives us F(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots = 1 + x + \frac{2!}{2!}x^2 + \frac{3!}{3!}x^3 + \cdots.  Thus, if we didn’t know it already, we can deduce that there are n! linear orders on n elements.

Furthermore, there is a notion of composition of species corresponding to composition of generating functions, where intuitively (\mathbf{F}\circ\mathbf{G})(S) is a partition of S together with a \mathbf{G}-structure on each element of the partition, and a \mathbf{F}-structure on the partition as a whole.

So why is differentiation meaningful?

What is the connection between differentiation of species and ordinary differentiation?  Two main ways of approaching ordinary differentiation are through limits or through infinitesimals.  There don’t seem to be any limits around, so let’s focus on infinitesimals.

Although you can make infinitesimals precise in various ways, most people who think about calculus using infinitesimals do so in a non-rigorous way.  Here’s one common non-rigorous principle:

Let \delta\neq 0 be such that \delta^2 = 0.  Then for any (smooth, real-valued) f and real x, f(x + \delta) = f(x) + \delta f'(x).

Of course, there is no such \delta in the standard definition of the real numbers.

Although this is non-rigorous, if we can translate the same non-rigorous principle over to species, that would give a good account of why differentiation shows up in generating functions.  The main insight is what the meaning of \delta should be.  The condition that \delta\neq 0 for species simply means that there should be at least one \delta-structure on some set.  The condition that \delta^2 = 0 is subtler: it means that you can’t put a \delta-structure on two sets at the same time.  As in the case with real numbers, this is impossible, but the reasoning works anyway so we’ll go with it.

Now let’s think about what f(x + \delta) means.  An (x+\delta)-structure on a set is either an x-structure or a \delta-structure.  By the definition of composition of species, an f(x+\delta)-structure on a set S is a partition of S together with an (x+\delta)-structure on each element of the partition and an f-structure on the partition as a whole.  This means that each element of the partition is given either an x-structure or a \delta-structure.

But, by the infinitesimal nature of \delta, at most one element of the partition can be given a \delta structure.  That means there are two cases: 0 elements of the partition have a \delta-structure or 1 does.  If 0 elements do, every element of the partition has an x-structure, and the species is f(x).  On the other hand, if one does, we can describe the species by saying which one does (with a hole in the f-structure) and what the \delta-structure was.  That’s \delta f'(x).  Therefore f(x + \delta) = f(x) + \delta f'(x)!

Note that if we didn’t know what the formula for a species with a hole was, we could go through the preceding informal reasoning and deduce that it should correspond to the derivative!  I don’t know if others are convinced, but I find this quite satisfying.  To be totally clear, as mentioned before, this argument came from sigfpe’s blog and I don’t know if it has history before that.

One thought on “Why is the derivative of a generating function meaningful?

  1. Hi, just letting you know: latex is broken in your comments sections. Whenever a latex expression occurs in a comment, instead of an image with the rendered latex, you get an image with the error message “latex path not specified” (although you can at least still read the latex via title/alt text).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s