##
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.

######
Problem 389

In ProblemÂ 373 what would the exponential generating function have been if we had asked for the number of ways to paint the poles with just one color of paint? With two colors of paint? What is the relationship between the EGF for painting the \(n\) poles with one color of paint and the EGF for painting the \(n\) poles with four colors of paint? What is the relationship between the EGF for painting the \(n\) poles with two colors of paint and the EGF for painting the poles with four colors of paint?

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{.}\)

######
Problem 390

What can you say about the relationship among the EGF for the number of permutations that are products of disjoint two-cycles and one-cycles, i.e., are involutions, the exponential generating function for the number of permutations that are the product of disjoint two-cycles only and the generating function for the number of permutations that are the product of disjoint one cycles only (these are identity permutations on their domain)?

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.

######
Problem 391

If we multiply the EGF for derangements times the EGF for the number of permutations whose cycle decompositions consist of one-cycles only, what EGF do we get? for what set of objects have we found the EGF?

HintNotice that any permutation is a product of a derangement of the elements not fixed by the permutation times a permutation whose cycle decomposition consists of 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.

######
Problem 392

What is the coefficient of \(\frac{x^n}{n!}\) in the product of two EGFs \(\sum_{i=0}^\infty a_i\frac{x^i}{i!}\) and \(\sum_{j=0}^\infty
b_j\frac{x^j}{j!}\text{?}\) (A summation sign is appropriate in your answer.)

HintA binomial coefficient is likely to appear in your answer.

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

Suppose that \(a_i\) is the number of ways to paint a set of \(i\) poles with red and white, and \(b_j\) is the number of ways to paint a set of \(j\) poles with blue, green, and yellow. In how many ways may we take a set \(N\) of \(n\) poles, divide it up into two sets \(I\) and \(J\) (using \(i\) to stand for the size of \(I\) and \(j\) to stand for the size of the set \(J\text{,}\) and allowing \(i\) and \(j\) to vary) and paint the poles in \(I\) red and white and the poles in \(J\) blue, green, and yellow? (Give your answer in terms of \(a_i\) and \(b_j\text{.}\) Don't figure out formulas for \(a_i\) and \(b_j\) to use in your answer; that will make it harder to get the point of the problem!) How does this relate to ProblemÂ 392?

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{.}\)

######
Problem 394

In ProblemÂ 383, why is the family of arrangements of set of books on a single shelf (assuming they all fit) a species?

######
Problem 395

In ProblemÂ 385, why is the family of people actually making phone calls (assuming nobody is calling outside the telephone network) at any given time, with the added relationship of who is calling whome, a species? Why is the family of sets of people who are not using their phones a species (with no additional construction needed)?

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{.}\)

######
Problem 396

Show that if \(\F\) and \(\mathcal{G}\) are species of structures on subsets of a set \(X\text{,}\) then the pair of structures of \(\F\cdot\mathcal{G}\) for a species of structures

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.

######
Problem 397

If \(\F\) and \(\mathcal{G}\) are species of subsets of \(X\text{,}\) how is the EGF for \(\F\cdot \mathcal{G}\) related to the EGFs for \(F\) and \(G\text{?}\) Prove you are right.

HintIf \(f(x) = \sum_{i=0}^\infty a_i \frac{x^i}{i!}\) and \(g(x) = \sum_{j=0}^\infty b_j\frac{x^j}{j!}\text{,}\) what is the coefficient of \(\frac{x^n}{n!}\) in \(f(x)g(x)\text{?}\) don't be surprised if your answer has a binomial coefficient in it. In fact, the binomial coefficient should help you finish the problem.

######
Problem 398

Without giving the proof, how can you compute the EGF \(f(x)\) for the number of structures using a set of size \(n\) in the species \(\F_1\cdot\F_2\cdot \cdots\cdot \F_k\) of structures on \(k\)-tuples of subsets of \(X\) from the EGFs \(f_i(x)\) for \(\F_i\) for each \(i\) from \(1\) to \(k\text{?}\) (Here we are using the natural extension of the idea of the pair of structures to the idea of a \(k\)-tuple structure.)

######
Theorem C.4.1

If \(\F_1, \F_2, \ldots, \F_n\) are species of subsets of the set \(X\) and \(\F_i\) has EGF \(f_i(x)\text{,}\) then the family of \(k\)-tuple structures \(\F_1\cdot \F_2\cdot \cdots\cdot \F_n\) has EGF \(\prod_{i=1}^n f_i(x)\text{.}\)

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.

######
Corollary C.4.2

If \(\F\) is a species of structures on subsets of \(X\) and \(f(x0)\) is the EGF for \(\F\text{,}\) then \(f(x)^k\) is the EGF for the \(k\)-tuple structure on \(k\)-tuples of \(\F\)-structures using disjoint subsets of \(X\text{.}\)

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.)

######
Corollary C.4.3

If \(\F\) is a species of structures on nonempty subsets of \(X\) and \(f(x)\) is the EGF for \(\F\text{,}\) then for each positive integer \(k\text{,}\) \(\frac{f(x)^k}{k!}\) is the EGF for the family \(\F^{(k)}\) of \(k\)-set structures on subsets of \(X\)

######
Problem 399

Prove CorollaryÂ C.4.3.

HintSince the sets of a \(k\)-set structure are nonempty and disjoint, the \(k\)-element set of sets can be arranged as a \(k\)-tuple in \(k!\) ways.

######
Problem 400

Use the product principle for EGFs to explain the results of ProblemsÂ 390 and ProblemÂ 391.

######
Problem 401

Use the general product principle for EGFs or one of its corollaries to explain the relationship between the EGF for painting streetlight poles in only one color and the EGF for painting streetlight poles in \(4\) colors in ProblemsÂ 373 and ProblemÂ 389. What is the EGF for the number \(p_n\) of ways to paint \(n\) streetlight poles with some fixed number \(k\) of colors of paint.

######
Problem 402

Use the general product principle for EGFs or one of its corollaries to explain the relationship between the EGF for arranging books on one shelf and the EGF for arranging books on \(n\) shelves in ProblemÂ 383.

######
Problem 403

(Optional) Our very first example of exponential generating functions used the binomial theorem to show that the EGF for \(k\)-element permutations of an \(n\) element set is \((1+x)^n\text{.}\) Use the EGF for \(k\)-element permutations of a one-element set and the product principle to prove the same thing. Hint: Review the alternate definition of a function in SectionÂ 3.1.2.

HintThe alternate definition of a funciton in SectionÂ 3.1.2 can be restated to say that a function from a \(k\)-element set \(K\) to an \(n\)-element set \(N\) can be thought of as an \(n\)-tuple of sets, perhaps with some empty, whose union is \(K\text{.}\) In order to think of the function as an \(n\)-tuple, we number the elements of \(N\) as number 1 through number \(n\text{.}\) Then the \(i\)th set in the \(n\)-tuple is the set of elements mapped to the \(i\)th element of \(N\) in our numbering?

######
Problem 404

What is the EGF for the number of ways to paint \(n\) streetlight poles red, white blue, green and yellow, assuming an even number of poles must be painted green and an even number of poles must be painted yellow? Give a formula for the number of ways to paint \(n\) poles. (Don't forget the factorial!)

HintDon't be surprised if you see a hyperbolic sine or hyperbolic cosine in your answer. If you aren't familiar with these functions, look them up in a calculus book.

######
Problem 405

What is the EGF for the number of functions from an \(n\)-element set onto a one-element set? (Can there be any functions from the empty set onto a one-element set?) What is the EGF for the number \(c_n\) of functions from an \(n\)-element set onto a \(k\) element set (where \(k\) is fixed)? Use this EGF to find an explicit expression for the number of functions from a \(k\)-element set onto an \(n\)-element set and compare the result with what you got by inclusion and exclusion.

######
Problem 406

In ProblemÂ 142 You showed that the Bell Numbers \(B_n\) satisfy the equation \(B_{n+1} =
\sum_{k=0}^{n} \binom{n}{k}B_{n-k}\) (or a similar equation for \(B_n\text{.}\)) Multiply both sides of this equation by \(\frac{x^n}{n!}\) and sum from \(n=0\) to infinity. On the left hand side you have a derivative of a certain EGF we might call \(B(x)\text{.}\) On the right hand side, you have a product of two EGFs, one of which is \(B(x)\text{.}\) What is the other one? What differential equation involving \(B(x)\) does this give you. Solve the differential equation for \(B(x)\text{.}\) This is the EGF for the Bell numbers!.

######
Problem 407

Prove that \(n2^{n-1} = \sum_{k=1}^n \binom{n}{k}k\) by using EGFs.

HintThe EGF for \(\sum_{i=1}^n\binom{n}{k}k\) is \(\sum_{n=1}^\infty \sum_{i=1}^n \frac{n!}{k!(n-k)!}k\frac{x^n}{n!}\text{.}\) You can cancel out the \(n!\) terms and the \(k\) terms. Now try to see if what is left can be regarded as the product of two EGFs.

######
Problem 408

In light of ProblemÂ 382, why is the EGF for the Stirling numbers \(S(n,k)\) of the second kind not \((e^x -1)^n\text{?}\) What is it equal to instead?