seven trees in one! and how laziness can be bad.

Sum divergent series, II, from The Everything Seminar. We learn

(1 + 1 + 2 + 5 + 14 + 42 + ...) = (1-√(-3))/2

in some sense (this follows from the usual generating function for the Catalan numbers, by letting z approach 1). This is a bit surprising, because we add a bunch of positive numbers and get something which isn't even real, but weird things happen with infinity. It turns out that this is a sixth root of unity, and therefore in some sense

(1 + 1 + 2 + 5 + 14 + 42 + ...)⁷ = (1 + 1 + 2 + 5 + 14 + 42 + ...)

which suggests that there ought to be a simple bijection between 7-tuples of trees (counted on the left) and trees (counted on the right). What that means is that we should be able take seven trees and in some way make one big tree out of them, and that furthermore this scheme is reversible -- that is, given the one big tree, we can determine which seven small trees it came from. And, in fact, there is! You can read about it here. The actual theorem is that "There is a very explicit bijection between the set of all seven-tuples of trees and the set of all trees", where "very explicit" has a certain technical sense. The bijection is fairly simple (see page 3) and takes about a quarter-page to specify; proving that is in, in fact, a bijection takes a page; the rest of the paper is taken up with describing why anyone would think such a crazy thing would exist in the first place.

A divergent series that comes up a lot in combinatorics is

P(z) = 1 + z + 2z² + 6z³ + 24z⁴ + 120z⁵ + ...

where the coefficients are the factorials; I don't know of any way to assign a meaningful number to this sum, although one might exist. It is the generating function of the permutations; that is, the coefficient of zⁿ is the number of permutations of [1, 2, ..., n], or the number of ways in which we can write the numbers from 1 to n in some order. It turns out that although this series is divergent, we can calculate with this in a useful way. For example, if we want to know the number of so-called indecomposable permutations, we can write

I(z) = 1 - 1/P(z)

where the division is in the sense of a formal power series, and then I(z) turns out to be the generating function of the indecomposable permutations. (The details can be found on p. 82 of Analytic Combinatorics by Flajolet and Sedgewick; the book is still in preparation, so the page number might change.) It would be possible to do this without using divergent generating functions -- but a lot harder. This is true of a lot of results with generating functions -- to transform a lot of basic combinatorics into routine computations. The advantage of this is clear -- by making problems that used to be hard into routine exercises, that frees up people to do more work that builds on those exercises. It's often been said that mathematicians are naturally lazy, which is a statement that might seem quite strange to the layperson. But what this means is that we try to come up with ways to automate a computation so that we don't actually have to do it ourselves. The unfortunate byproduct of this is that it often seems that doing the actual computation is useful for getting a feeling for the problem. If I were actually doing some work that involved indecomposable permutations, I would almost certainly write them out for, say, n=3 and n=4; that would give me more of an intuitive sense for the problem, even if it would be a very inefficient way to work if I just wanted to know how many of them there are.