GILA IV: The unreasonable effectiveness of generating functions in the combinatorial sciences

We’ve got everything we need to prove the Polya enumeration theorem. To state the theorem, however, requires the language of generating functions, so I thought I’d take the time to establish some of the important ideas. It isn’t possible to do justice to the subject in one post, so I’ll start with some references.

Many people recommend Wilf’s generatingfunctionology, but the terminology is non-standard and somewhat problematic. Nevertheless, it has valuable insight and examples.

I cannot recommend Flajolet and Sedgewick’s Analytic Combinatorics highly enough. It is readable, includes a wide variety of examples as well as very general techniques, and places a great deal of emphasis on asymptotics, computation, and practical applications.

If you can do the usual computations but want to learn some theory, Bergeron, Labelle, and Laroux’s Combinatorial Species and Tree-like Structures is a fascinating introduction to the theory of species that requires fairly little background, although a fair amount of patience. It also contains my favorite proof of Cayley’s formula.

Doubilet, Rota, and Stanley’s On the idea of generating function is part of a fascinating program for understanding generating functions with posets as the fundamental concept. I may have more to say about this perspective once I learn more about it.

While it is by no means comprehensive, this post over at Topological Musings is a good introduction to the basic ideas of species theory.

And a shameless plug: the article I wrote for the Worldwide Online Olympiad Training program about generating functions is available here. I tried to include a wide variety of examples and exercises taken from the AMC exams while focusing on techniques appropriate for high-school problem solvers. There are at least a few minor errors, for which I apologize. You might also be interested in this previous post of mine.

In any case, this post will attempt to be a relatively self-contained discussion of the concepts necessary for understanding the PET.

The first big trick of generating function theory is to study a sequence by studying the (formal or analytic) power series called its ordinary generating function (ogf)

.

(When we call a power series formal, we are ignoring questions of convergence.) This has several advantages, some of which are obvious and some of which are quite deep.

1. If is the number of “constructions” of a certain type on a set with cardinality , then addition and multiplication of series corresponds directly to two natural operations on constructions: addition of two series gives the number of constructions of either the first type or the other, whereas multiplication of series gives the number of constructions where part of the set is a construction of the first type and part of the set is a construction of the second type. This observation is one of the big motivations for species theory. For example, the generating function that describes the probability of rolling various sums by rolling six-sided dice simultaneously is

   

   in the sense that the coefficient of tells us the probability of rolling a sum of . This is due to the fact that the additions tell us that a dice roll is either a one or a two or…, and the multiplications tell us that a sum consists of rolling the first die and the second die and…. Think carefully about why this works; it’s essentially an extension of the usual combinatorial interpretation of the binomial theorem.

2. Many natural operations on sequences, such as taking finite differences or partial sums, are easily describable in terms of generating functions. For example, taking forward differences is equivalent to multiplying by and taking partial sums is equivalent to dividing by .
3. It’s often possible to express recursions for in terms of equations that its generating function must satisfy, which may involve derivatives, and so to translate the computation of (if you are only given a recursion) into the problem of finding a function satisfying a certain functional equation or differential equation. For example, the recursive definition of the Catalan numbers, as I have mentioned, is equivalent to the identity

   

   for their ogf. Even if it doesn’t appear feasible to solve a functional equation, various analytic methods such as the Lagrange inversion theorem can still be used to extract coefficients.

4. Often a sequence does not have a nice “closed form” but still has a nice generating function. There are rather deep reasons for this phenomenon generally related to how certain well-known functions can be interpreted combinatorially. For example, the Bell numbers count the number of ways to partition a set into a disjoint union of subsets. While it does not have a particularly nice closed formula, we have the exponential generating function (egf)

   .

   The distinction between exponential and ordinary generating functions occurs depending on whether we’re counting “labeled” or “unlabeled” objects, but for now the basic idea is that certain sequences grow too fast for their ogf’s to be nice. There are both high-level and low-level proofs of the above result; hopefully we’ll get into the high-level ones sooner or later.

5. Generating functions that correspond to analytic functions can be studied in terms of the analytic properties of the function. This is the main tool of asymptotic analysis, and in many cases it’s possible to give extremely precise estimates for values of sequences that don’t have anything approaching a nice closed form. For example, using a basic property of meromorphic functions, it’s possible to show that the fraction of permutations of elements with only cycles of length greater than or equal to is asymptotically equal to . Flajolet and Sedgewick is the best reference I know of for such techniques.

The non-analytic benefits of using generating functions can roughly be summarized as follows: generating functions are a way to rephrase combinatorial arguments using algebraic tools.

A general way to construct a generating function is as follows: we have an infinite set , such as the set of all binary trees, along with a combinatorial parameter sometimes called a weight taking values in, say, the non-negative integers, such that there are finitely many with a particular value of . We can then construct the weight enumerator

.

The coefficient of in this generating function then counts the number of such that . For binary trees, one usually takes to be the total number of vertices in the tree.

Weight enumerators behave very nicely under disjoint union and Cartesian product if one adopts two reasonable conventions:

1. The weight of an element in a disjoint union is inherited from the original set to which it belonged.
2. The weight of an element in a Cartesian product is the sum of the weights of its components.

With these two conventions, addition of series corresponds to disjoint union and multiplication of series corresponds to Cartesian product. If the sets involved are finite, one recovers “unweighted” disjoint union and Cartesian product by setting .

The nice thing about thinking about generating functions from this perspective is that there’s no reason to stick to one parameter. Thus we can introduce a family of parameters and construct a multivariate generating function

.

The coefficient of then counts the number of such that . Introducing extra parameters is a straightforward way to generalize a known counting result. If you know how a set splits up with respect to one parameter, see how each term of the one-variable generating function splits up with respect to a second parameter.

One key to working with combinatorial parameters is this: most combinatorial arguments interact nicely with the obvious parameters. Thus the same counting argument can prove both a one-variable identity or a multivariate identity.

Now would be a good time for an example. One way to define the Fibonacci numbers is as follows: is the number of ways to walk a distance if you can only walk in steps of length . The obvious combinatorial parameter is the total length of the walk. One can compute the generating function as follows: every walk is either empty, consists of a step of length followed by another walk, or consists of a step of length followed by another walk. This argument is equivalent to the weighted identity

which immediately gives . An interesting combinatorial parameter to introduce now is the number of steps of length . This gives the weighted identity

which immediately gives . The coefficient of is now a polynomial called a Fibonacci polynomial; for positive integer values of , it counts the number of tilings where the tiles of size can take on one of different colors. (This is another good reason to introduce combinatorial parameters.) The Fibonacci polynomials are closely related to the Chebyshev polynomials, which is characteristic of the relationship between combinatorics and the theory of special functions.

Sometimes the interesting parameters to introduce aren’t obvious. (Sometimes they become obvious only when the combinatorial object being studied is bijected to a different one; this is a good reason to like bijective combinatorics.) For example, a classical parameter to study when looking at permutations is the number of inversions of the permutation. The inversion statistic counts the number of pairs of letters in the word that are “out of order” from the identity word .

Proposition: the weight enumerator is equal to the -factorial .

The proof is quite elegant. We build up the word of a permutation as follows: first, we write down a . Next, we have a choice about where to write down the . The first choice introduces no inversion and the second choice introduces one inversion. More generally, when we choose where to write down , each of our chooses introduces inversions respectively. This argument is equivalent to the weighted identity

as desired. What’s the connection to Young diagrams that fit inside a box? I should probably know this, but my first guess is that it probably has something to do with the fact that

counts partitions into parts of size at most , i.e. Young diagrams of width (equivalently, height) at most . I would be very interested if anyone could give a direct proof relating this result to the Young diagram result.

I could go on and on, but if you understood the above examples then you’re already in a position to rediscover the PET. The question you want to ask yourself: does the argument we used to prove baby Polya interact nicely with the extra parameters “number of times this color is used”?

Exercises

(For additional exercises, consult my article or any of the other references.)

A Motzkin tree or binary-unary tree is a tree in which every non-leaf node has either one or two children. Compute the generating function of the Motzkin trees indexed by the total number of vertices in the tree.

Let be a generating function with no constant term. What does the generating function count? (Hint: two equivalent ways to think about this generating function are as or as the unique generating function satisfying . If it helps, think about the case that is a polynomial with non-negative integer coefficients.)

Given variables , the elementary symmetric functions are defined as the coefficients of the polynomial

.

The power symmetric functions are defined as the coefficients of the power series

.

Finally, the complete homogeneous symmetric functions are defined as the coefficients of the power series

.

Show that each of these sequences of polynomials can be written in terms of the others. What happens to the first and third sequences at ? What are the first and third sequences generating functions of?