Appendix C: Exponential Generating Functions

C.1: Indicator Functions

When we introduced the idea of a generating function, we said that the formal sum

\(\sum_{i=0}^{n} a_ix^i\)

may be thought of as a convenient way to keep track of the sequence \(a_i\). We then did quite a few examples that showed how combinatorial properties of arrangements counted by the coefficients in a generating function could be mirrored by algebraic properties of the generating functions themselves. The monomials \(x^i\) are called indicator polynomials. (They indicate the position of the coefficient \(a_i\).) One example of a generating function is given by

\((1 + x)^n = \sum_{i=0}^{\infty} \binom{n}{i} x^i \).

Thus we say that \((1+ x)^n\) is the generating function for the binomial coefficients \( \binom{n}{i} \). The notation tells us that we are assuming that only \(i\) varies in the sum on the right, but that the equation holds for each fixed integer \(n\). This is implicit when we say that \((1+ x)^n\) is the generating function for \( \binom{n}{i} \), because we haven’t written i anywhere in \((1+ x)^n\), so it is free to vary.

Another example of a generating function is given by

\(x^{\underline{n}} = \sum_{i=0}^{\infty} s(n, i)x^i\).

Thus we say that \(x^n\) is the generating function for the Stirling numbers of the first kind, \(s(n, i)\). There is a similar equation for Stirling numbers of the second kind, namely

\(x^n = \sum_{i=0}^{\infty} S(n, i)x^{\underline{i}}\)

However, with our previous definition of generating functions, this equation would not give a generating function for the Stirling numbers of the second kind, because \(S(n, i)\) is not the coefficient of \(x^i\). If we were willing to consider the falling factorial powers \(x^i\) as indicator polynomials, then we could say that \(x^n\) is the generating function for the numbers \(S(n, i)\) relative to these indicator polynomials. This suggests that perhaps different sorts of indicator polynomials go naturally with different sequences of numbers.

The binomial theorem gives us yet another example.

This example suggests that we could say that \((1+x)^n\) is the generating function for the falling factorial powers \(n^{\underline{i}}\) relative to the indicator polynomials \(\dfrac{x^i}{i!}\). In general, a sequence of polynomials is called a family of indicator polynomials if there is one polynomial of each nonnegative integer degree in the sequence. Those familiar with linear algebra will recognize that this says that a family of indicator polynomials form a basis for the vector space of polynomials. This means that each polynomial way can be expressed as a sum of numerical multiples of indicator polynomials in one and only one way. One could use the language of linear algebra to define indicator polynomials in an even more general way, but a definition in such generality would not be useful to us at this point.

C.2: Exponential Generating Functions

We say that the expression \( \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\) is the exponential generating function for the sequence \(a_i\). It is standard to use EGF as a shorthand for exponential generating function. In this context, we call the generating function \( \sum_{i=0}^{n} a_i x^i\) that we originally studied the ordinary generating function for the sequence \(a_i\). You can see why we use the term exponential generating function by thinking about the exponential generating function (EGF) for the all ones sequence,

\[ \sum_{i=0}^{\infty} 1 \dfrac{x^i}{i!} = \sum_{i=0}^{\infty} \dfrac{x^i}{i!} = e^x,\]

which we also denote by \(\exp(x)\). Recall from calculus that the usual definition of \(e^x\) or \(\exp(x)\) involves limits at least implicitly. We work our way around that by defining \(e^x\) to be the power series \(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\).

C.3: Applications to Recurrences.

We saw that ordinary generating functions often play a role in solving recurrence relations. We found them most useful in the constant coefficient case. Exponential generating functions are useful in solving recurrence relations where the coefficients involve simple functions of \(n\), because the \(n!\) in the denominator can cancel out factors of \(n\) in the numerator.

C.4: The Product Principle for EGFs

One of our major tools for ordinary generating functions was the product principle. It is thus natural to ask if there is a product principle for exponential generating functions. In Problem 383 you likely found that the EGF for the number of ways of arranging \(\)n books on one shelf was exactly the same as the EGF for the number of permutations of \([n]\), namely \(\dfrac{1}{1−x}\) or \((1 − x)^{−1}\). Then using our formula from Problem 122 and the generating function for multisets, you probably found that the EGF for number of ways of arranging \(n\) books on some fixed number \(m\) of bookshelves was \((1 − x)^{−m}\). Thus the EGF for \(m\) shelves is a product of \(m\) copies of the EGF for one shelf.

In Problem 385 you likely found that the EGF for the number of network configurations with \(n\) customers was \(e^{\frac{x+x^2}{2}} = e^x · e^{\frac{x^2}{2}}\). In Problem 380 you saw that the generating function for the number of permutations on \(n\) elements that are products of one cycles was \(e^x\), and in Problem 378 you likely found that the EGF for the number of tennis pairings of \(2n\) people, or equivalently, the number of permutations of \(2n\) objects that are products of \(n\) two-cycles is \(e^{\frac{x^2}{2}}\).

In Problem 388 you likely found that the EGF for the number of permutations of \([n]\) that are derangements is \(e^{\frac{−x}{1−x}}\). But every permutation is a product of derangements and one cycles, because the permutation that sends \(i\) to \(i\) is a one-cycle, so that when you factor a permutation as a product of disjoint cycles, the cycles of size greater than one multiply together to give a derangement, and the elements not moved by the permutation are one-cycles.

We now have four examples in which the EGF for a sequence or a pair of objects is the product of the EGFs for the individual objects making up the sequence or pair.

In the case of painting streetlight poles in Problem 389, let us examine the relationship between the EGF for painting poles with two colors, the EGF for painting the poles with three colors, and the EGF for painting poles with five colors, \(e^{5x}\). To be specific, the EGF for painting poles red and white is \(e^{2x}\) and the EGF for painting poles blue, green, and yellow is \(e^{3x}\). To decide how to paint poles with red, white, blue, green, and yellow, we can decide which set of poles is to be painted with red and white, and which set of poles is to be painted with blue, green, and yellow. Notice that the number of ways to paint a set of poles with red and white depends only on the size of that set, and the number of ways to paint a set of poles with blue, green, and yellow depends only on the size of that set.

Problem 393 shows that the formula you got for the coefficient of \(\dfrac{x^n}{n!}\) in the product of two EGFs is the formula we get by splitting a set \(N\) of poles into two parts and painting the poles in the first part with red and white and the poles in the second part with blue, green, and yellow. More generally, you could interpret your result in Problem 392 to say that the coefficient of \(\dfrac{x^n}{n!}\) in the product \(\sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!} \sum_{j=0}^{\infty} b_j \dfrac{x^j}{j!}\) of two EGFs is the sum, over all ways of splitting a set \(N\) of size \(n\) into an ordered pair of disjoint sets \(I\) and \(J\), of the product \(a_{|I|} b_{|J|}\).

There seem to be two essential features that relate to the product of exponential generating functions. First, we are considering structures that consist of a set and some additional mathematical construction on or relationship among the elements of that set. For example, our set might be a set of light poles and the additional construction might be a coloring function defined on that set. Other examples of additional mathematical constructions or relationships on a set could include a permutation of that set; in particular an involution or a derangement, a partition of that set, a graph on that set, a connected graph on that set, an arrangement of the elements of that set around a circle, or an arrangement of the elements of that set on the shelves of a bookcase. In fact, a set with no additional construction or arrangement on it is also an example of a structure. Its additional construction is the empty set! When a structure consists of the set \(S\) plus the additional construction, we say the structure uses \(S\). What all the examples we have mentioned in our earlier discussion of exponential generating functions have in common is that the number of structures that use a given set is determined by the size of that set. We will call a family \(\mathcal{F}\) of structures a species of structures on subsets of a set \(X\) if structures are defined on finite subsets of \(X\) and if the number of structures in the family using a finite set \(S\) is finite and is determined by the size of \(S\) (that is, if there is a bijection between subsets \(S\) and \(T\) of \(X\), the number of structures in the family that use \(S\) equals the number of structures in the family that use \(T\)). We say a structure is an \(\mathcal{F}\)-structure if it is a member of the family \(\mathcal{F}\).

The second essential feature of our examples of products of EGFs is that products of EGFs seem to count structures on ordered pairs of two disjoint sets (or more generally on \(k\)-tuples of mutually disjoint sets). For example, we can determine a five-coloring of a set \(S\) by partitioning it in all possible ways into two sets and coloring the first set in the pair with our first two colors and our second pair with the last three colors. Or we can partition our set in all possible ways into five parts and color part i with our ith color. We don’t have to do the same thing to each part of our partition; for example, we could define a derangement on one part and an identity permutation on the other; this defines a permutation on the set we are partitioning, and we have already noted that every permutation arises in this way.

Our combinatorial interpretation of EGFs will involve assuming that the coefficient of \(\dfrac{x^i}{i!}\) counts the number of structures on a particular set of of size \(i\) in a species of structures on subsets of a set \(X\). Thus in order to give an interpretation of the product of two EGFs we need to be able to think of ordered pairs of structures on disjoint sets or \(k\)-tuples of structures on disjoint sets as structures themselves. Thus, given a structure on a set \(S\) and another structure on a disjoint set \(T\), we define the ordered pair of structures (which is a mathematical construction!) to be a structure on the set \(S ∪ T\). We call this a pair structure on \(S ∪ T\). We can get many structures on a set \(S ∪ T\) in this way, because \(S ∪ T\) can be divided into many other pairs of disjoint sets. In particular, the set of pair structures whose first structure comes from \(\mathcal{F}\) and whose second element comes from \(\mathcal{G}\) is denoted by \(\mathcal{F} · \mathcal{G}\).

Given a species \(\mathcal{F}\) of structures, the number of structures using any particular set of size \(i\) is the same as the number of structures in the family using any other set of size \(i\). We can thus define the exponential generating function (EGF) for the family as the power series \(\sum_{i=1}^{\infty} a_i \dfrac{x^i}{i!}\), where \(a_i\) is the number of structures of \(\mathcal{F}\) that use one particular set of size \(i\). In Problems 372, 373, 376, 377, 378, 380, 382, 383, 387, and 388, we were computing EGFs for species of subsets of some set.

We call Theorem C.4.1 the product principle for exponential generating functions. We give two corollaries; the proof of the second is not immediate though not particularly difficult.

Our next corollary uses the idea of a \(k\)-set structure. Suppose we have a species \(\mathcal{F}\) of structures on nonempty subsets of \(X\), that is, a species of structures which assigns no structures to the empty set. Then we can define a new species \(\mathcal{F}^{(k)}\) of structures, called “\(k\)-set structures,” using nonempty subsets of \(X\). Given a fixed positive integer \(k\), a \(k\)-set structure on a subset \(Y\) of \(X\) consists of a \(k\)-element set of nonempty disjoint subsets of \(X\) whose union is \(Y\) and an assignment of an \(\mathcal{F}\)-structure to each of the disjoint subsets. This is a species on the set of subsets of \(X\); the subset used by a \(k\)-set structure is the union of the sets of the structure. To recapitulate, the set of \(k\)-set structures on a subset \(Y\) of \(X\) is the set of all possible assignments of \(\mathcal{F}\)-structures to \(k\) nonempty disjoint sets whose union is \(Y\). (You can also think of the \(k\)-set structures as a family of structures defined on blocks of partitions of subsets of \(X\) into \(k\) blocks.)

C.5: The Exponential Formula

Exponential generating functions turn out to be quite useful in advanced work in combinatorics. One reason why is that it is often possible to give a combinatorial interpretation to the composition of two exponential generating functions. In particular, if \(f(x) = \sum_{i=0}^{n} a_i \dfrac{x^i}{i!}\) and \(g(x) = \sum_{j=1}^{\infty} b_j \dfrac{x^j}{j!}\), it makes sense to form the composition \(f(g(x))\) because in so doing we need add together only finitely many terms in order to find the coefficient of \(\dfrac{x^n}{n!}\) in \(f(g(x))\) since in the EGF \(g(x)\) the dummy variable \(j\) starts at \(1\). Since our study of combinatorial structures has not been advanced enough to give us applications of a general formula for the composition of the EGF, we will not give here the combinatorial interpretation of this composition. However we have seen some examples where one particular composition can be applied. Namely, if \(f(x) = e^x = \exp(x)\), then \(f(g(x)) = \exp(g(x))\) is well defined when \(b_0 = 0\). We have seen three examples in which an EGF is \(e^{f (x)}\) where \(f(x)\) is another EGF. There is a fourth example in which the exponential function is slightly hidden.

There was one element that our last four problems had in common. In each case, our EGF \(f(x)\) involved the number of structures of a certain type (partitions, telephone networks, tennis pairings, permutations) that used only one set of an appropriate kind. (That is, we had a partition with one part, a telephone network consisting either of one person or two people connected to each other, a tennis pairing of one set of two people, or a permutation with one cycle.) Our EGF \(g(x)\) was the number of structures of the same “type” (we put type in quotation marks here because we don’t plan to define it formally) that could consist of any number of sets of the appropriate kind. Notice that the order of these sets was irrelevant. For example, we don’t order the blocks of a partition and a product of disjoint cycles is the same no matter what order we use to write down the product. Thus we were relating the EGF for structures which were somehow “building blocks” to the EGF for structures which were sets of building blocks. For a reason that you will see later, it is common to call the building blocks connected structures. Notice that our connected structures were all based on nonempty sets, so we had no connected structures whose value was the empty set. Thus in each case, if \(f(x) = \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\), we would have \(a_0 = 0\). The relationship between the EGFs was always \(g(x) = e^{f(x)}\). We now give a combinatorial explanation for this relationship.

In Problem 413, we proved the following theorem, which is called the exponential formula.

Let us see how the exponential formula applies to the examples in Problems 409, 410, 411 and 412. In Problem 382 our family \(\mathcal{F}\) should consist of one-block partitions of finite subsets of a set, say the set of natural numbers. Since a partition of a set is a set of blocks whose union is \(S\), a one-block partition whose block is \(B\) is the set \(\{B\}\). Then any nonempty finite subset of the positive integers is the value of exactly one structure in \(\mathcal{F}\). (There is no one-block partition of the empty set, so we have no structures using the empty set.) As you showed in Problem 382 the generating function for partitions with just one block is \(e^{x} − 1\). Thus, by the exponential formula, \(\exp(e^x−1)\) is the EGF for sets of subsets of the positive integers whose values are disjoint sets whose union is any particular set \(N\) of size \(n\). This set of disjoint sets partitions the set \(N\). Thus \(\exp(e^x − 1)\) is the EGF for partitions of sets of size \(n\). (As we wrote our description, it is the EGF for partitions of \(n\)-element subsets of the positive integers, but any two \(n\)-element sets have the same number of partitions.) In other words, \(\exp(e^x − 1)\) is the exponential generating function for the Bell numbers \(B_n\).

One of the most spectacular applications of the exponential formula is also the reason why, when we regard a combinatorial structure as a set of building block structures, we call the building block structures connected. In Chapter 2, we introduced the idea of a connected graph and in Problem 104 we saw examples of graphs which were connected and were not connected. A subset C of the vertex set of a graph is called a connected component of the graph if

• every vertex in \(C\) is connected to every other vertex in that set by a walk whose vertices lie in \(C\), and
• no other vertex in the graph is connected by a walk to any vertex in \(C\).

In Problem 241, we showed that each connected component of a graph consists of a vertex and all vertices connected to it by walks in the graph.

The last sequence of problems shows that we may think of any graph as the set of its connected component graphs. (Once we know them, we know all the vertices and all the edges of the graph). Notice that a graph is connected if and only if it has exactly one connected component. Since the connected components form a partition of the vertex set of a graph, the exponential formula will relate the EGF for the number of connected graphs on \(n\) vertices with the EGF for the number of graphs (connected or not) on \(n\) vertices. However because we can draw as many edges as we want between two vertices of a graph, there are infinitely many graphs on \(n\) vertices, and so the problem of counting them is uninteresting. We can make it interesting by considering simple graphs, namely graphs in which each edge has two distinct endpoints and no two edges connect the same two vertices. It is because connected graphs form the building blocks for viewing all graphs as sets of connected components that we refer to the building blocks for structures counted by the EGF in the exponential formula as connected structures.

The point to the last problem is that we can use the exponential formula in reverse to say that if \(g(x)\) is the generating function for the number of (nonempty) connected structures of size \(n\) in a given family of combinatorial structures and \(f(x)\) is the generating function for all the structures of size \(n\) in that family, then not only is \(f(x) = e^{g(x)}\), but \(g(x) = \ln(f(x))\) as well. Further, if we happen to have a formula for either the coefficients of \(f(x)\) or the coefficients of \(g(x)\), we can get a formula for the coefficients of the other one!

C.6: Supplementary Problems

1. Use product principle for EGFs and the idea of coloring a set in two colors to prove the formula \(e^x · e^x = e^{2x}\).

2. Find the EGF for the number of ordered functions from a \(k\)-element set to an \(n\)-element set.

3. Find the EGF for the number of ways to string \(n\) distinct beads onto a necklace.

4. Find the exponential generating function for the number of broken permutations of a \(k\)-element set into \(n\) parts.

5. Find the EGF for the total number of broken permutations of a \(k\)-element set.

6. Find the EGF for the number of graphs on \(n\) vertices in which every vertex has degree \(2\).

7. Recall that a cycle of a permutation cannot be empty.

a. What is the generating function for the number of cycles on an even number of elements (i.e. permutations of an even number \(n\) of elements that form an n-cycle)? Your answer should not have a summation sign in it. Hint: If \(y = \sum_{i=0}^{\infty} \dfrac{x^{2i}}{2i}\), what is the derivative of \(y\)?

b. What is the generating function for the number of permutations on \(n\) elements that are a product of even cycles?

c. What is the generating function for the number of cycles on an odd number of elements?

d. What is the generating function for the number of permutations on \(n\) elements that are a product of odd cycles?

e. How do the generating functions in parts b and d of this problem related to the generating function for all permutations on \(n\) elements?

Notes

a. It is possible to define the derivatives and integrals of power series by the formulas \[\dfrac{d}{dx} \sum_{i=0}^{\infty} b_ix^i = \sum_{i=1}^{\infty} ib_ix^{i-1}\] and \[\int_{0}^{x} \sum_{i=0}^{\infty} b_ix^i = \sum_{i=0}^{\infty} \dfrac{b_i}{i+1}x^{i+1} \] rather than by using the limit definitions from calculus. It is then possible to prove that the sum rule, product rule, etc. apply. (There is a little technicality involving the meaning of composition for power series that turns into a technicality involving the chain rule, but it needn’t concern us at this time.)