The combinatorics of basic calculus

Filed on Today, at 6:19 am

Much of this post is inspired by Doron Zeilberger's insightful entry in the Princeton Companion to Mathematics.

If we all learned combinatorics before we learned calculus perhaps we would be more inclined to ask the following very basic question: where do the factorials in a Taylor series expansion really come from?

Factorials must clearly count permutations, and yet it is never really explained what permutations have to do with power series expansions. The proof that the $n^{th}$ derivative of $x^n$ is $n!$ is elementary enough, and yet that only changes the question: what combinatorial significance does differentiation have?

This question clearly has something to do with why exponential generating functions are useful and important. One of the reason one prefers an EGF to an OGF is that the underlying object being counted is "labeled": for example, the number of labeled sets with $n$ elements (and $n$ labels) is $a_n = n!$ , which has exponential generating function

$A(x) = \sum_{n \ge 0} \frac {a_n}{n!} x^n = \frac {1}{1 - x}$ .

By comparison, there is not much useful one can say about the ordinary generating function $\sum n! x^n$ . Its radius of convergence is $0$ , and even in the combinatorial frame of mind where we don't care about convergence this is bad news since we know it won't actually correspond to a function we can work with.

I'd like to work a few more examples. The number of words of length $n$ selected from an alphabet of $s$ letters is $s^n$ , which has exponential generating function

$S(x) = \sum_{n \ge 0} \frac {s^n}{n!} x^n = e^{sx}$ .

In particular, the number of words of length $n$ selected from an alphabet of $1$ letter is our good friend the exponential. What significance does this have for differentiation? It's easy to count words of length $n$ by recursion: you start with a word of length $n - 1$ and add a letter to the end. In other words,

$s^n = s \cdot s^{n - 1}.$

In the language of exponential generating functions, differentiation corresponds to a shift in index (this is what we're really going after) and the above is equivalent to the identity

$\frac {d}{dx} e^{sx} = s e^{sx}.$

So something genuinely combinatorial is going on here. Let's try something else. The number of words of length $n$ from an alphabet of $s + r$ letters is, by the above definition, $e^{(s + r)}x} = e^{sx} e^{rx}$ . We've seen the natural definition of multiplying exponential generating functions before: it is the convolution

$c_n = \sum_{k = 0}^{n} {n \choose k} a_k b_{n - k}$

that picks a labeled object of size $k$ from $A$ and a labeled object of size $n - k$ from $B$ to form a labeled object of size $n$ and then decides where to permute the two accordingly. Here, a word from an alphabet of $s + r$ letters is obtained from two words, one from an alphabet of $s$ letters and one from an alphabet of $r$ letters, which are then permuted. So we can think of the factorial factors as accounting for these permutations.

The above definition is missing something. Given only a definition of $a_k$ , what is being "permuted"? The answer is that we should regard at least some of the EGFs of labeled objects as counting the number of ways we can put "connected components" of some other basic object together. Here, the basic object is a letter, of which there are $s$ of size one: hence the EGF of the set of letters is $sx$ . Given an EGF $a(x)$ for a set of basic objects, $a(x)^n$ (by the above argument) counts the number of ordered $n$ -tuples of objects from $a$ of a given size: we then divide out by $n!$ (this is very promising!) because we only care about the collection itself, and then sum over all $n$ to obtain

The Fundamental Theorem of Exponential Generating Functions: If $a(x)$ is the EGF of a collection of basic objects subject to the condition $a(0) = 0$ , let $A(x)$ denote the EGF of disjoint unions of basic objects. Then

$A(x) = \sum_{n \ge 0} \frac {a(x)^n}{n!} = e^{a(x)}.$

(The condition that $a(0) = 0$ is necessary to ensure that the computation of $A(x)$ occurs formally: otherwise the computation of $A(0)$ requires the notion of convergence.)

This is marvelous! Notice how beautifully this subsumes all of our previous discussion. Given two EGFs $a(x), b(x)$ of two kinds of connected components (say, two alphabets with disjoint letters), $a(x) + b(x)$ is just their union, and the exponential of that counts the number of ways we can put $a$ -components and $b$ -components together, hence the above provides a combinatorial proof that $e^{a + b} = e^a e^b$ . Even the first example we treated can be understood in this manner: $n!$ counts the number of permutations, a permutation is a disjoint union of cycles, and the number of cycles of length $k$ is (fixing a base point) $(k - 1)!$ , hence

$a(x) = \sum_{k \ge 0} \frac {(k - 1)!}{k!} x^k = - \ln (1 - x)$

and

$A(x) = e^{a(x)} = \frac {1}{1 - x}$

exactly as originally discussed. Hence we have a combinatorial proof of the power series of the natural log. (Since it takes non-connected things to connected things, there is a sense in which the power series of the natural log is another instance of PIE; we'll see a fun application of this later.) Returning to differentiation, one basic calculus notion is the product rule

$(fg)' = f g' + f' g$

which we'd like to prove combinatorially. If we know what $f, g$ count, we know what $fg$ counts. It was suggested earlier that $f', g'$ are just index shifts; to be more precise, if $f$ is the EGF of $f_n$ then $f'$ is the EGF of $f_{n + 1}$ . Following the approach the Wikipedia article on combinatorial species, we can think of this as adding an extra element before counting: hence the product rule reduces to the very simple observation that when we differentiate $fg$ we can add an extra element that is either of $f$ type or of $g$ type. For example, applied to $e^{sx}, e^{rs}$ it gives

$(e^{(s + r)x})' = se^{sx} e^{rx} + re^{sx} e^{rx}$

which is the very simple statement that when we add an extra letter it can be from the alphabet of $s$ letters or from the alphabet of $r$ letters. For this reason it is also fruitful to think of the product rule as a special case of the chain rule

$f(g)' = f'(g) g'$

which we would, again, like to prove combinatorially. When $f = e^x$ , this is the statement that

$(e^g)' = e^g g'$ ;

in other words, adding an element to the set of disjoint unions of "basic elements" $g$ is done by starting with a smaller disjoint union of basic elements $e^g$ and then adding another basic element (after reindexing appropriately). There is an interpretation of composition for more general EGFs $f$ where $f(g)$ denotes the set of " $f$ -structures on $g$ ": when $f = e^x$ , the EGF of the number of words on a singleton alphabet, this reduces to the fundamental theorem; the Wiki article has the details.

One last remark. It now appears (at least to me) that the theory of ordinary generating functions is a special case of the theory of exponential generating functions, for the following reason: whenever $a_n$ counts an unlabeled combinatorial family, we can attach labels to form the sequence $n! a_n$ whose EGF is precisely the OGF of the original sequence. Thus the multiplication of OGFs is a special case of the multiplication of EGFs (as is readily verified) and so forth. For example, the Catalan numbers count rooted binary trees with $n + 1$ leaves, and labeling those leaves gets us the quadruple factorial numbers. In the language of species, the sequences for which OGFs are nice have permutation group all of $S_n$ .

-------------------------------

Some applications.

As mentioned before, $\frac {1}{1 - x}$ is the EGF of $f_n = n!$ ; that is, it counts the number of permutations, or labeled sets, of $n$ elements. How many labeled sets with "basic objects" of size $1$ or $2$ are there? For labeling reasons, the EGF to use here is $g(x) = x + x^2$ because we can think of the basic object of size $2$ with $2!$ sets of labels on it; this fits well with the idea that OGFs are EGFs in disguise. (A precise definition of "label" is given in the Wiki article: roughly, there is a way to make precise the notion that it doesn't matter what the labels are; that is, the definition of a species is functorial. They can be numbers or colors or other combinatorial objects.) This gives the answer as

$f(g) = \frac {1}{1 - x - x^2} = \sum_{n \ge 0} F_{n + 1} x^n$ ,

precisely the (shifted) Fibonacci numbers as we already knew, that is, the number of tilings of a $1 \times n$ grid with $1 \times 1$ and $1 \times 2$ tiles (where we have multiplied by $n!$ because of labeling). This directly suggests the identity

$F_{n + 1} = \sum_{j \ge 0} {n - j \choose j}$

obtained by writing $f(g) = \sum_{n \ge 0} (x + x^2)^n$ and applying the binomial theorem; we've already seen the combinatorial proof here. The cool thing about this technique is that it allows us to prove combinatorial identities about a linear recurrence without computing the roots of its characteristic polynomial: for example, if we want basic objects of size $1$ or $3$ , we get $g(x) = x + x^3$ and the answer is

$f(g) = \frac {1}{1 - x - x^3} = \sum_{n \ge 0} G_n x^n = \sum_{n \ge 0} (x + x^3)^n$

which immediately gives, by the binomial theorem or combinatorial reasoning, the identity

$G_n = \sum_{j \ge 0} {n - 2j \choose j}$

even though we haven't computed the roots of the characteristic polynomial or the analogue of the Fibonacci polynomials. If we want basic objects of any positive integer size, we get $g(x) = x + x^2 + ... = \frac {x}{1 - x}$ , which gives

$f(g) = \frac {1}{1 - \frac {x}{1 - x}} = \frac {1 - x}{1 - 2x} = 1 + \sum_{n \ge 1} 2^{n - 1} x^n.$

What does it mean to ask for a tiling with tiles of any size? It simply means to place a number of dividers between the tiles, and the number of ways to do this is obviously $2^\text{number of spots between tiles}$ (or $1$ if there aren't any tiles). Can you extend this to a combinatorial proof that the set of fractional linear transformations is closed under composition? (The fractional linear transformations are precisely the generating functions of geometric series with a possibly different first term.) An "infinite" extension is given in the Practice Problems.

If we allow two "colors" of basic objects, we can ask, for example, what happens if we allow $r$ types of basic red object of size $1$ and $s$ types of basic blue object of size $1$ : then the generating function should be the product

$\frac {1}{(1 - rx)(1 - sx)} = \frac {1}{r - s} \left( \frac {1}{1 - rx} - \frac {1}{1 - sx} \right) = \sum_{n \ge 0} \frac {r...$

although we have to keep in mind that what this product counts is the number of ordered pairs of red tilings and blue tilings with a fixed total size. This generating function is easily explained as follows: it is the sum $\sum_{k = 0}^{n - 1} r^k s^{n - 1 - k}$ , so we have yet again provided a combinatorial proof of the geometric series formula. Can you extend this to a combinatorial proof of partial fraction decomposition?

Now let's think about unlabeled sets. The Bell numbers $B_n$ count the number of partitions of $\{ 1, 2, ... n \} = [n]$ , equivalently, the number of equivalence relations. We can think of a partition as a disjoint union of nonempty sets. The EGF of the nonempty sets is $e^x - 1$ (there is no nonempty set of size $0$ ), hence by the fundamental theorem we obtain

$\sum_{n \ge 0} B_n \frac {x^n}{n!} = e^{e^x - 1}$ .

Taking the derivative tells us that

$B_{n + 1} = \sum_{k = 0}^{n} {n \choose k} B_k$

which we can also deduce combinatorially as follows: given a partition of $[n + 1]$ , the partition that $n + 1$ belongs to has some size $(n + 1) - k$ , and removing it gives a partition of some $k$ -element subset of $[n]$ .

To further elucidate the distinction between labeled and unlabeled sets, let's see what happens if we look at the "number of labeled collections of unlabeled nonempty sets," whatever that means. The EGF is

$f(g) = \frac {1}{2 - e^x} = \frac {1}{2} \sum_{k \ge 0} \frac {e^{kx}}{2^k} = \sum_{\ge 0} \frac {M_n}{n!} x^n$

which gives $M_n = \sum_{k \ge 0} \frac {k^n}{2^k}$ . This is interesting! You might recognize $M_1$ as the expected number of coin tosses $k$ before you toss a heads, and generally you can think of $M_k$ as the expected value of $k^n$ , which is a certain kind of moment.

Before we analyze this EGF, let's stop and think about what the powers of $g$ mean. The powers of $e^x$ are obvious: if $e^x$ is the number of unlabeled sets, $(e^x)^k = e^{kx}$ is the number of ways we can take $k$ unlabeled sets (each with objects that are considered disjoint from the others) - say, in $k$ colors - and permute them together, hence the number of words on $k$ letters as we saw before. When we take powers of $e^x - 1$ we disallow the empty set for any given letter (color), i.e.

$(e^x - 1)^k = \sum_{j = 0}^{k} ( - 1)^j {k \choose j} e^{jx}$

counts the number of words on $k$ letters such that each letter is used at least once. The above identity is then an instance of the Principle of Inclusion-Exclusion.

We can now describe what $M_n$ counts. If we number the colors (letters) $1, 2, 3, ...$ (there are countably many of them now), then $M_n$ is the number of words of length $n$ such that if letter $k$ is used at least once, then every letter $i, i < k$ is also used. This sequence does not appear to have a great name, but it is the number of ways $n$ competitors can place in a competition if we allow ties (where letter $k$ becomes $k^{th}$ place), which is a very succinct interpretation. The places define a weak order on $n$ elements, although it's not clear what all this has to do with moments of coin tosses. I'd be interested if someone could explain this to me. As for the closed form, I'll go with a link for now.

Another example is due to Zeilberger: returning to the observation that a permutation is a disjoint union of cycles, we'd like to count the number of permutations with exactly $k$ cycles. This can be done by assigning a weight $y$ to each cycle, i.e. to replace $- \ln (1 - x)$ with $- y \ln (1 - x)$ , which then gives the generating function

$e^{ - y \ln (1 - x)} = \frac {1}{(1 - x)^y} = \sum_{n \ge 0} { - y \choose n} ( - x)^n = \frac {y...(y + (n - 1))}{n!} x^n$

which gives the answer as the coefficient of $y^k$ in a rising factorial; this is the definition of the Stirling numbers of the first kind, up to sign. Compare with the earlier discussion on Newton polynomials. (There is, according to Stanley, a sense in which negative binomial coefficients having combinatorial significance is the result of a combinatorial reciprocity theorem, but I am far from understanding this point.)

Now suppose we'd instead like to count the number of permutations with exactly $k$ fixed points. This can be done by assigning a weight $y$ to the $1$ -cycles, i.e. to replace $- \ln (1 - x)$ with $- \ln (1 - x) - x + yx$ . This gives

$e^{ - \ln(1 - x) - x + yx} = \frac {1}{1 - x} e^{yx - x} = \sum_{n \ge 0} \frac {F_n(y)}{n!} x^n$

where $F_n(y) = \sum_{k = 0}^{n} D_{n,k} y^k = \sum_{\pi \in S_n} y^{\text{Fix}(\pi)}$ is the polynomial generating function of the rencontres numbers. On the other hand, clearly

$\frac {1}{1 - x} e^{yx - x} = \frac {1}{1 - x} \sum_{n \ge 0} \left( \sum_{k = 0}^{n} {n \choose k} y^k ( - 1)^{n - k}} \righ...$

which gives $D_{n,k} = \sum_{i = 0}^{n} {i \choose k} ( - 1)^{i - k} \frac {n!}{i!}$ , another instance of PIE. In the case $k = 0$ we obtain $D_{n,0} = n! \sum_{i = 0}^{n} ( - 1)^i \frac {1}{i!} \approx \frac {n!}{e}$ , a well-known formula for derangements. Substituting $y = 0$ gives the corresponding generating function.

Let $I_n$ denote the permutations of $[n]$ of order dividing $2$ (i.e. involutions). Such a permutation consists of $1$ -cycles and $2$ -cycles only. These have EGF $x + \frac {x^2}{2}$ , hence by the fundamental theorem the answer is

$\sum_{n \ge 0} \frac {I_n}{n!} x^n = e^{x + \frac {x^2}{2} }.$

While this is not a familiar function, having this generating function makes it easy to deduce other properties of $I_n$ . Differentiating, we obtain the identity

$I_{n + 1} = I_n + n I_{n - 1}$

which we can deduce combinatorially as follows: in an involution of $[n + 1], n + 1$ is either a fixed point or belongs to a cycle of length $2$ . Generally, the number of permutations of $[n]$ of order dividing $k$ has EGF

$\text{exp} \left( \sum_{d | k} \frac {x^d}{d} \right).$

The EGF of the number of involutions in $S_n$ with no fixed points is

$\sum_{n \ge 0} \frac {I_n'}{n!} x^n = e^{\frac {x^2}{2} }$ .

It's not hard to see why: this implies that $I_{2n}' = \frac {(2n!)}{2^n n!} = 1 \cdot 3 \cdot 5 \cdot ... \cdot (2n - 1)$ , which is easy to give a combinatorial interpretation to via the recurrence $I_{2n} = (2n - 1) I_{2n - 2}$ : in an involution of $[2n]$ with no fixed points, $2n$ belongs to a $2$ -cycle. I'm curious what all this has to do with the normal distribution.

Finally, let me give an example of using the fundamental theorem in the other direction. The number of labeled simple graphs on $n$ vertices is obviously $2^{\frac {n(n - 1)}{2} }$ (two pairs of vertices either have or don't have an edge); note that this is much easier than talking about the number of unlabeled simple graphs since we must deal with graph isomorphisms. This generating function is

$G(x) = \sum_{n \ge 0} 2^{\frac {n(n - 1)}{2} } \frac {x^n}{n!}$ .

This suggests that the logarithm of the above generating function, which begins

$\log G(x) = x + \frac {x^2}{2!} + \frac {4x^3}{3!} + \frac {38x^4}{4!} + \frac {728x^5}{5!} + ...$ ,

must count the number of (nonempty) connected simple graphs on $n$ vertices, which in fact is true. There is, as far as I know, no simpler way to describe this generating function.

-------------------------------

Practice Problem 1: Compute the coefficients of $e^{\frac {x}{1 - x} }$ ; what does this EGF count?

Practice Problem 2: The Euler zigzag numbers count the number of permutations $\delta_1, ... \delta_n$ such that $\delta_1 < \delta_2 > \delta_3 < \delta_4 > ...$ . Show that

$2A_{n + 1} = \sum_{k = 0}^{n} {n \choose k} A_k A_{n - k}$

and from there deduce the exponential generating function $\sum_{n \ge 0} \frac {A_n}{n!} x^n$ . (It is a sum of two functions with which you should be very familiar!)

Practice Problem 3: Prove that a sequence $s_n$ that satisfies a linear recurrence with polynomial (rather than constant) coefficients has EGF satisfying a differential equation, also with polynomial coefficients.

Practice Problem 4: Keeping in mind the discussion of $f(x) = \frac {1}{1 - x}$ , prove that

$\sum_{n \ge 0} C_n x^n = \frac {1}{1 - \frac {x}{1 - \frac {x}{1 - \frac {x}{1 - ...}}}}$

where $C_n$ are the Catalan numbers. What do the convergents, interpreted as OGFs, count?

*Practice Problem 5: Prove, first by generating functions, and then combinatorially, the identity

$\sum_{\pi \in S_n} \text{Fix}(\pi)^k = B_{k,n} n!$

where $B_{k,n}$ is the number of partitions of $[k]$ into at most $n$ parts and $\text{Fix}(\pi)$ is the number of fixed points of $\pi$ .

*Practice Problem 6 (Putnam 2005 B6): Let $\sigma(\pi)$ denote the signature of a permutation $\pi \in S_n$ . Show that

$\sum_{\pi \in S_n} \frac {\sigma(\pi)}{\text{Fix}(\pi) + 1} = ( - 1)^{n + 1} \frac {n}{n + 1}$ .

Hint: See if you can modify the generating function of the rencontres numbers.

Practice Problem 7: See this thread.

(Post your comment)

5 Comments have been made

t0rajir0u wrote: It now appears (at least to me) that the theory of ordinary generating functions is a special case of the theory of exponential generating functions

No, they're a special case of Fourier transforms. The essence of a transform method is that it relates convolution on one side to pointwise multiplication on the other. More specifically, ordinary generating functions are the discretized version of the Laplace transform.
OK, I'm not really serious- but combinatorics isn't everything, especially when working with ideas like generating functions designed to cross boundaries.

Posted Thu Feb 19, 2009 12:45 am, by jmerry

Very elegant and readable

Beautiful and interesting, thanks Smile

Posted Thu Feb 19, 2009 3:33 pm, by bambaman

Book on EGFs

This was an amazing post, very readable and informative! But unfortunately, I got lost somewhere along the counting of labelled objects. Could you please recommend a book that goes more indepth into EGFs than Generatingfunctionology by Herbert S. Wilf ? And one that has many examples ? Thank you.

Posted Tue Feb 24, 2009 11:26 pm, by bloops

An interesting observation on problem 2

Problem 2 is quite interesting in more ways than you mentioned. For example, it's known that $\int \sec x \, dx = \ln(\sec x + \tan x)$ . Since the operations of integration, exponentiation, and the functions involved all have combinatorial meaning, it's actually possible to come up with a (not terribly contrived) combinatorical proof of this identity. I discussed this once last year with Dennis Chebikin (who shared with me the above observation), and we agreed that it should actually be possible to reconstruct a fair amount of trigonometry combinatorially from identities like this. Unfortunately, I think this may fall into the category of "things that would be really cool if someone else could do them and summarize the results for me," but not into the category of "things that are sufficiently interesting that I'll try to do them myself." I wonder if I could convince some ambitious undergraduate to give it a try .... Wink