Combinatorics Through Guided Discovery

Section 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]\text{,}\) namely \(\frac{1}{1-x}\) or \((1-x)^{-1}\text{.}\) 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}\text{.}\) 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^{x+x^2/2}= e^x \cdot e^{x^2/2}\text{.}\) 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\text{,}\) 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^{x^2/2}\text{.}\)

In Problem 388 you likely found that the EGF for the number of permutations of \([n]\) that are derangements is \(\frac{e^{-x}}{1-x}\text{.}\) 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}\text{.}\) 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}\text{.}\) 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 \(\frac{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 \(\frac{x^n}{n!}\) in the product \(\sum_{i=0}^\infty a_i \frac{x^i}{i!} \sum_{j=0}^\infty b_j\frac{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\text{,}\) of the product \(a_{|I|}b_{|J|}\text{.}\)

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\text{.}\) 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 \(\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\text{,}\) 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 \(\F\)-structure if it is a member of the family \(\F\text{.}\)

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 \(\frac{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\text{.}\) 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\text{,}\) we define the ordered pair of structures (which is a mathematical construction!) to be a structure on the set \(S\cup T\text{.}\) We call this a pair structure on \(S\cup T\text{.}\) We can get many structures on a set \(S\cup T\) in this way, because \(S\cup T\) can be divided into many other pairs of disjoint sets. In particular, the set of pair structures whose first structure comes from \(\F\) and whose second element comes from \(\mathcal{G}\) is denoted by \(\F\cdot \mathcal{G}\text{.}\)

Given a species \(\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\text{.}\) We can thus define the exponential generating function (EGF) for the family as the power series \(\sum_{i=1}^\infty a_i \frac{x^i}{i!}\text{,}\) where \(a_i\) is the number of structures of \(\F\) that use one particular set of size \(i\text{.}\) In Problems 372, 373, 376, 377, 378, 380, 382, 383, 387, and 388, we were computaing 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 particular difficult.

Our next corollary uses the idea of a \(k\)-set structure. Suppose we have a species \(\F\) of structures on nonempty subsets of \(X\text{,}\) that is, a species of structures which assigns no structures to the empty set. Then we can define a new species \(\F^{(k)}\) of structures, called “\(k\)-set structures,” using nonempty subsets of \(X\text{.}\) Given a fixed positive integer \(k\text{,}\) 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 \(\F\)-structure to each of the disjoint subsets. This is a species on the set of subsets of \(X\text{;}\) 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 \(\F\)-structures to \(k\) nonempty disjoint sets whose union is \(Y\text{.}\) (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.)