The combinatorics of basic calculus
by t0rajir0u, Feb 19, 2009, 4:53 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
derivative of
is
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
elements (and
labels) is
, which has exponential generating function
.
By comparison, there is not much useful one can say about the ordinary generating function
. Its radius of convergence is
, 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
selected from an alphabet of
letters is
, which has exponential generating function
.
In particular, the number of words of length
selected from an alphabet of
letter is our good friend the exponential. What significance does this have for differentiation? It's easy to count words of length
by recursion: you start with a word of length
and add a letter to the end. In other words,

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

So something genuinely combinatorial is going on here. Let's try something else. The number of words of length
from an alphabet of
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

that picks a labeled object of size
from
and a labeled object of size
from
to form a labeled object of size
and then decides where to permute the two accordingly. Here, a word from an alphabet of
letters is obtained from two words, one from an alphabet of
letters and one from an alphabet of
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
, 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
of size one: hence the EGF of the set of letters is
. Given an EGF
for a set of basic objects,
(by the above argument) counts the number of ordered
-tuples of objects from
of a given size: we then divide out by
(this is very promising!) because we only care about the collection itself, and then sum over all
to obtain
The Fundamental Theorem of Exponential Generating Functions: If
is the EGF of a collection of basic objects subject to the condition
, let
denote the EGF of disjoint unions of basic objects. Then

(The condition that
is necessary to ensure that the computation of
occurs formally: otherwise the computation of
requires the notion of convergence.)
This is marvelous! Notice how beautifully this subsumes all of our previous discussion. Given two EGFs
of two kinds of connected components (say, two alphabets with disjoint letters),
is just their union, and the exponential of that counts the number of ways we can put
-components and
-components together, hence the above provides a combinatorial proof that
. Even the first example we treated can be understood in this manner:
counts the number of permutations, a permutation is a disjoint union of cycles, and the number of cycles of length
is (fixing a base point)
, hence

and

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

which we'd like to prove combinatorially. If we know what
count, we know what
counts. It was suggested earlier that
are just index shifts; to be more precise, if
is the EGF of
then
is the EGF of
. 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
we can add an extra element that is either of
type or of
type. For example, applied to
it gives

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

which we would, again, like to prove combinatorially. When
, this is the statement that
;
in other words, adding an element to the set of disjoint unions of "basic elements"
is done by starting with a smaller disjoint union of basic elements
and then adding another basic element (after reindexing appropriately). There is an interpretation of composition for more general EGFs
where
denotes the set of "
-structures on
": when
, 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
counts an unlabeled combinatorial family, we can attach labels to form the sequence
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
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
.
Some applications.
As mentioned before,
is the EGF of
; that is, it counts the number of permutations, or labeled sets, of
elements. How many labeled sets with "basic objects" of size
or
are there? For labeling reasons, the EGF to use here is
because we can think of the basic object of size
with
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
,
precisely the (shifted) Fibonacci numbers as we already knew, that is, the number of tilings of a
grid with
and
tiles (where we have multiplied by
because of labeling). This directly suggests the identity

obtained by writing
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
or
, we get
and the answer is

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

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
, which gives

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
(or
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
types of basic red object of size
and
types of basic blue object of size
: then the generating function should be the product

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
, 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
count the number of partitions of
, 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
(there is no nonempty set of size
), hence by the fundamental theorem we obtain
.
Taking the derivative tells us that

which we can also deduce combinatorially as follows: given a partition of
, the partition that
belongs to has some size
, and removing it gives a partition of some
-element subset of
.
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

which gives
. This is interesting! You might recognize
as the expected number of coin tosses
before you toss a heads, and generally you can think of
as the expected value of
, which is a certain kind of moment.
Before we analyze this EGF, let's stop and think about what the powers of
mean. The powers of
are obvious: if
is the number of unlabeled sets,
is the number of ways we can take
unlabeled sets (each with objects that are considered disjoint from the others) - say, in
colors - and permute them together, hence the number of words on
letters as we saw before. When we take powers of
we disallow the empty set for any given letter (color), i.e.

counts the number of words on
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
counts. If we number the colors (letters)
(there are countably many of them now), then
is the number of words of length
such that if letter
is used at least once, then every letter
is also used. This sequence does not appear to have a great name, but it is the number of ways
competitors can place in a competition if we allow ties (where letter
becomes
place), which is a very succinct interpretation. The places define a weak order on
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
cycles. This can be done by assigning a weight
to each cycle, i.e. to replace
with
, which then gives the generating function

which gives the answer as the coefficient of
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
fixed points. This can be done by assigning a weight
to the
-cycles, i.e. to replace
with
. This gives

where
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}} \right) \frac {x^n}{n!}$
which gives
, another instance of PIE. In the case
we obtain
, a well-known formula for derangements. Substituting
gives the corresponding generating function.
Let
denote the permutations of
of order dividing
(i.e. involutions). Such a permutation consists of
-cycles and
-cycles only. These have EGF
, hence by the fundamental theorem the answer is

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

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

The EGF of the number of involutions in
with no fixed points is
.
It's not hard to see why: this implies that
, which is easy to give a combinatorial interpretation to via the recurrence
: in an involution of
with no fixed points,
belongs to a
-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
vertices is obviously
(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
.
This suggests that the logarithm of the above generating function, which begins
,
must count the number of (nonempty) connected simple graphs on
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
; what does this EGF count?
Practice Problem 2: The Euler zigzag numbers count the number of permutations
such that
. Show that

and from there deduce the exponential generating function
. (It is a sum of two functions with which you should be very familiar!)
Practice Problem 3: Prove that a sequence
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
, prove that

where
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

where
is the number of partitions of
into at most
parts and
is the number of fixed points of
.
*Practice Problem 6 (Putnam 2005 B6): Let
denote the signature of a permutation
. Show that
.
Hint: See if you can modify the generating function of the rencontres numbers.
Practice Problem 7: See this thread.
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



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




By comparison, there is not much useful one can say about the ordinary generating function


I'd like to work a few more examples. The number of words of length




In particular, the number of words of length





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

So something genuinely combinatorial is going on here. Let's try something else. The number of words of length



that picks a labeled object of size








The above definition is missing something. Given only a definition of









The Fundamental Theorem of Exponential Generating Functions: If




(The condition that



This is marvelous! Notice how beautifully this subsumes all of our previous discussion. Given two EGFs









and

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

which we'd like to prove combinatorially. If we know what












which is the very simple statement that when we add an extra letter it can be from the alphabet of



which we would, again, like to prove combinatorially. When


in other words, adding an element to the set of disjoint unions of "basic elements"







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




Some applications.
As mentioned before,









precisely the (shifted) Fibonacci numbers as we already knew, that is, the number of tilings of a





obtained by writing





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

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


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


If we allow two "colors" of basic objects, we can ask, for example, what happens if we allow





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

Now let's think about unlabeled sets. The Bell numbers

![$ \{ 1, 2, ... n \} = [n]$](http://latex.artofproblemsolving.com/9/8/6/986a195ff5d8ef6bc29df33a237fb917c11ee19f.png)



Taking the derivative tells us that

which we can also deduce combinatorially as follows: given a partition of
![$ [n + 1]$](http://latex.artofproblemsolving.com/6/5/b/65bfeade6fc043f4ecdebde41d2fc7fcfb0121d0.png)



![$ [n]$](http://latex.artofproblemsolving.com/8/6/f/86f3c9726ae54305ce8de9304a59c227951947a5.png)
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

which gives





Before we analyze this EGF, let's stop and think about what the powers of









counts the number of words on

We can now describe what










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





which gives the answer as the coefficient of

Now suppose we'd instead like to count the number of permutations with exactly






where

$ \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}} \right) \frac {x^n}{n!}$
which gives




Let

![$ [n]$](http://latex.artofproblemsolving.com/8/6/f/86f3c9726ae54305ce8de9304a59c227951947a5.png)





While this is not a familiar function, having this generating function makes it easy to deduce other properties of


which we can deduce combinatorially as follows: in an involution of
![$ [n + 1], n + 1$](http://latex.artofproblemsolving.com/7/4/9/7497f47e5d2b7b5bf6d5ac170598374e3826e8e5.png)

![$ [n]$](http://latex.artofproblemsolving.com/8/6/f/86f3c9726ae54305ce8de9304a59c227951947a5.png)


The EGF of the number of involutions in


It's not hard to see why: this implies that


![$ [2n]$](http://latex.artofproblemsolving.com/9/6/5/965c914a12624d87db0daca7c2243641ef2b2ae2.png)


Finally, let me give an example of using the fundamental theorem in the other direction. The number of labeled simple graphs on



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

must count the number of (nonempty) connected simple graphs on

Practice Problem 1: Compute the coefficients of

Practice Problem 2: The Euler zigzag numbers count the number of permutations



and from there deduce the exponential generating function

Practice Problem 3: Prove that a sequence

Practice Problem 4: Keeping in mind the discussion of


where

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

where

![$ [k]$](http://latex.artofproblemsolving.com/c/d/b/cdbcbc5bebb2e1903ba8e493df41bec0748ed0ad.png)



*Practice Problem 6 (Putnam 2005 B6): Let



Hint: See if you can modify the generating function of the rencontres numbers.
Practice Problem 7: See this thread.