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\frac{x^i}{i!}\) and \(g(x) = \sum_{j=1}^\infty b_j \frac{x^j}{j!}\text{,}\) 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 \(\frac{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)\text{,}\) then \(f(g(x)) =\ exp(g(x))\) is well defined when \(b_0=0\text{.}\) 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.
If \(f(x)\) is the EGF for the number of partitions of an \(n\)-set into one block, and \(g(x)\) is the EGF for the total number of partitions of an \(n\)-element set, that is, for the Bell numbers \(B_n\text{,}\) how are the two generating functions related?
Let \(f(x)\) be the EGF for the number of permutations of an \(n\)-element set with one cycle of size one or two. What is \(f(x)\text{?}\) What is the EGF \(g(x)\) for the number of permutations of an \(n\)-element set all of whose cycles have size one or two, that is, the number of involutions in \(S_n\text{?}\) How are these two exponential generating functions related?
Let \(f(x)\) be the EGF for the number of permutations of an \(n\)-element set that have exactly one two-cycle and no other cycles. Let \(g(x)\) be the EGF for the number of permutations which are products of two-cycles only, that is, for tennis pairings. (That is, they are not a product of two-cycles and a nonzero number of one-cycles). What is \(f(x)\text{?}\) What is \(g(x)\text{?}\) How are these to exponential generating functions related?
Let \(f(x)\) be the EGF for the number of permutations of an \(n\)-element set that have exactly one cycle. (This is the same as the EGF for the number of ways to arrange \(n\) people around a round table.) Let \(g(x)\) be the EGF for the total number of permutations of an \(n\)-element set. What is \(f(x)\text{?}\) What is \(g(x)\text{?}\) How are \(f(x)\) and \(g(x)\) related?
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\frac{x^i}{i!}\text{,}\) we would have \(a_0=0\text{.}\) The relationship between the EGFs was always \(g(x) = e^{f(x)}\text{.}\) We now give a combinatorial explanation for this relationship.
Suppose that \(\F\) is a species of structures of a set \(X\) with no structures on the empty set. Let \(f(x)\) be the EGF for \(\F\text{.}\)
In the power series
what does Corollary C.4.3 tell us about the coefficient of \(\frac{x^n}{n!}\) in \(\frac{f(x)^k}{k!}\text{?}\)
What does the coefficient of \(\frac{x^n}{n!}\) in \(e^{f(x)}\) count?
In Problem 413 we proved the following theorem, which is called the exponential formula.
Suppose that \(\F\) is a species of structures on subsets of a set \(X\) with no structures on the empty set. Let \(f(x)\) be the EGF for \(\F\text{.}\) Then the coefficient of \(\frac{x^n}{n!}\) in \(e^{f(x)}\) is the number of sets of structures on disjoint sets whose union is a particular set of size \(n\text{.}\)
Let us see how the exponential formula applies to the examples in Problems 409, 410, 411 and 412. In Problem 382 our family \(\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\text{,}\) a one-block partition whose block is \(B\) is the set \(\{B\}\text{.}\) Then any nonempty finite subset of of the positive integers is the value of exactly one structure in \(\F\text{.}\) (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\text{.}\) 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\text{.}\) This set of disjoint sets partitions the set \(N\text{.}\) Thus \(\exp(e^x-1)\) is the EGF for partitions of sets of size \(n\text{.}\) (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\text{.}\)
Explain how the exponential formula proves the relationship we saw in Problem 412.
Explain how the exponential formula proves the relationship we saw in Problem 411.
Explain how the exponential formula proves the relationship we saw in Problem 410.
In Problem 373 we saw that the generating function for the number of ways to use five colors of paint to paint \(n\) light poles along the north side of Main Street in Anytown was \(e^{4x}\text{.}\) We should expect an explanation of this EGF using the exponential formula. Let \(\F\) be the family of all one-element sets of light poles with the additional construction of an ordered pair consisting of a light pole and a color. Thus a given light pole occurs in five ordered pairs. Put no structures on any other finite set. Show that this is a species of structures on the finite subsets of the positive integers. What is the exponential generating function \(f(x)\) for \(\F\text{?}\) Assuming that there is no upper limit on the number of light poles, what subsets of \(S\) does the exponential formula tell us are counted by the coefficient of \(x^n\) in \(e^{f(x)}\text{?}\) How do the sets being counted relate to ways to paint light poles?
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\text{,}\) and
no other vertex in the graph is connected by a walk to any vertex in \(C\text{.}\)
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.
Show that every vertex of a graph lies in one and only one connected component of a graph. (Notice that this shows that the connected components of a graph form a partition of the vertex set of the graph.)
Explain why no edge of the graph connects two vertices in different connected components.
Explain why it is that if \(C\) is a connected component of a graph and \(E'\) is the set of all edges of the graph that connect vertices in \(C\text{,}\) then the graph with vertex set \(C\) and edge set \(E'\) is a connected graph. We call this graph a connected component graph of the original 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.
Suppose that \(f(x) = \sum_{n=0}^\infty c_n \frac{x^n}{n!}\) is the exponential generating function for the number of simple connected graphs on \(n\) vertices and \(g(x) = \sum_{i=0}^\infty a_i \frac{x^i}{i!}\) is the exponential generating function for the number of simple graphs on \(i\) vertices. From this point onward, any use of the word graph means simple graph.
Is \(f(x) = e^{g(x)}\text{,}\) is \(f(x) = e^{g(x)-1}\text{,}\) is \(g(x) = e^{f(x)-1}\) or is \(g(x) = e^{f(x)}\text{?}\)
To apply the exponential formula, we must take the exponential function of an EGF whose constant term is zero, or in other words, for a species of structures that has no structures that use the empty set.
One of \(a_i\) and \(c_n\) can be computed by recognizing that a simple graph on a vertex set \(V\) is completely determined by its edge set and its edge set is a subset of the set of two element subsets of \(V\text{.}\) Figure out which it is and compute it.
Once you know the vertex set of a graph, all you have to do to specify the graph is to specify its set of edges.
Write \(g(x)\) in terms of the natural logarithm of \(f(x)\) or \(f(x)\) in terms of the natural logarithm of \(g(x)\text{.}\)
Write \(\log(1+y)\) as a power series in \(y\text{.}\)
What is the calculus definition of \(\log(1+y)\text{?}\)
Why is the coefficient of \(\frac{x^0}{0!}\) in \(g(x)\) equal to one? Write \(f(x)\) as a power series in \(g(x) -1\text{.}\)
You can now use the previous parts of the problem to find a formula for \(c_n\) that involves summing over all partitions of the integer \(n\text{.}\) (It isn't the simplest formula in the world, and it isn't the easiest formula in the world to figure out, but it is nonetheless a formula with which one could actually make computations!) Find such a formula.
Look for a formula that involves summing over all partitions of the integer \(n\text{.}\)
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)}\text{,}\) 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)\text{,}\) we can get a formula for the coefficients of the other one!
