$\newcommand{\cycle}{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## SectionC.4The 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.

###### Problem389

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{.}$

###### Problem390

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.

###### Problem391

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?

Hint

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

###### Problem392

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

Hint

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.

###### Problem393

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{.}$

###### Problem394

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

###### Problem395

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{.}$

###### Problem396

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.

###### Problem397

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.

Hint

If $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.

###### Problem398

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

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

###### Problem399

Prove Corollary C.4.3.

Hint

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

###### Problem400

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

###### Problem401

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.

###### Problem402

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.

###### Problem403

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

Hint

The 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?

###### Problem404

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

Hint

Don'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.

###### Problem405

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.

###### Problem406

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

###### Problem407

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

Hint

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

###### Problem408

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?