Deep understanding on exponential generating function

In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?

We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.

Here I'd like to give an indication which structures do we count when applying the binomial convolution \begin{align*} \sum_{k=0}^n\binom{n}{k}b_kc_{n-k} \end{align*} of two exponential generating functions $B(z)=\sum_{j=0}^\infty b_j \frac{z^j}{j!}$ and $C(z)=\sum_{k=0}^\infty c_k\frac{z^k}{k!}$.

Permutations: We introduce a universe $\mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,\ldots,n$. We also add an empty permutation $\varepsilon$ of length $0$ and consider \begin{align*} \mathcal{P}=\{\varepsilon,1,12,21,123,132,213,231,312,321,\ldots\}\tag{1} \end{align*}

The coefficients $a_n$ of the corresponding exponential generating function $A(z)=\sum_{n=0}^\infty a_n \frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain \begin{align*} \color{blue}{A(z)}=\sum_{n=0}^\infty n!\frac{z^n}{n!}=\sum_{n=0}^\infty z^n\color{blue}{=\frac{1}{1-z}} \end{align*}

• We observe that generating functions like $\frac{1}{1-z}$ may serve as both, ordinary generating functions \begin{align*} \frac{1}{1-z}=\sum_{n=0}^\infty z^n=\color{blue}{1}+\color{blue}{1}\cdot z+\color{blue}{1}\cdot z^2+\color{blue}{1}\cdot z^3+\cdots \end{align*} to count for instance a sequence of unary words \begin{align*} \mathcal{S}=\{\varepsilon,\bullet,\bullet\bullet,\bullet\bullet\bullet,\ldots\}\tag{2} \end{align*}

• as well as exponential generating functions \begin{align*} \frac{1}{1-z}=\sum_{n=0}^\infty n!\frac{z^n}{n!}=\color{blue}{0!}+\color{blue}{1!}\cdot \frac{z}{1!}+\color{blue}{2!}\cdot \frac{z^2}{2!}+\color{blue}{3!}\cdot \frac{z^3}{3!}+\cdots \end{align*} to count permutations according to (1).

• Note, the simplicity of the geometric series $\frac{1}{1-z}=1+z+z^2+\cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.

Warmup: Multiplicative structure of ordinary generating functions.

We consider $\mathcal{B}=\{\bullet,\bullet\bullet\bullet\},\mathcal{C}=\{\bullet,\bullet\bullet\}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule \begin{align*} \color{blue}{\mathrm{card}\left(\mathcal{B}\times \mathcal{C}\right)=\mathrm{card}\left(\mathcal{B}\right)\cdot \mathrm{card}\left(\mathcal{C}\right)} \end{align*} the set $\mathcal{A}=\{(\bullet,\bullet),(\bullet,\bullet\bullet),(\bullet\bullet\bullet,\bullet),(\bullet\bullet\bullet,\bullet\bullet)\}$ and the following relationship \begin{align*} A(z)&=\sum_{a\in\mathcal{A}}z^{|a|}=\sum_{(\beta,\gamma)\in(\mathcal{B}\times\mathcal{C})}z^{|\beta|+|\gamma|} =\left(\sum_{\beta\in \mathcal{B}}z^{|\beta|}\right)\times\left(\sum_{\gamma\in \mathcal{C}}z^{|C|}\right)=B(z)\cdot C(z)\\ A(z)&=z^2+z^3+z^4+z^5\\ &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=\left(z^1+z^3\right)\times\left(z^1+z^2\right)=(z+z^3)(z+z^2) \end{align*} which follows from distributing products over sums.

Multiplicative structure of exponential generating functions:

In order to cover the binomial convolution $\sum_{k=0}^n\binom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.

We consider $\mathcal{B}=\{123,213\},\mathcal{C}=\{12\}$ with generating functions $B(z)=2\frac{z^3}{3!}, C(z)=\frac{z^2}{2!}$ and consider the multiplicative rule \begin{align*} \color{blue}{\mathcal{B}\star\mathcal{C}=\bigcup_{\beta\in\mathcal{B},\gamma\in\mathcal{C}}\left(\beta\star\gamma\right)}\tag{3} \end{align*} which is defined as:

• The labelled product (3) of $\mathcal{B}$ and $\mathcal{C}$, denoted $\mathcal{B}\star\mathcal{C}$, is obtained by forming ordered pairs from $B\star C$ and performing all possible order-consistent relabellings.

The last phrase all possible order-consistent relabellings needs to be explained. With the example $\mathcal{B}=\{123,213\}$ and $\mathcal{C}=\{12\}$ we perform a relabeling.

At first we start with a relabelling and select wlog $\mathcal{C}=\{45\}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows \begin{align*} \mathcal{B}\star\mathcal{C}&=\bigcup_{\beta\in\mathcal{B},\gamma\in\mathcal{C}}\left(\beta\star\gamma\right)\\ &=\left(\{123\}\star\{45\}\right)\cup\left(\{213\}\star\{45\}\right)\\ &=\{12345,12435,12534,13425,13524,14523,23415,23514,24513,34512\}\tag{4}\\ &\qquad\cup\{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512\}\tag{5}\\ \end{align*}

When looking at the set $\{123\}\star\{45\}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $\binom{5}{3}=10$ strings of length $3$ from $\{1,2,3,4,5\}$ which follow the order $1<2<3$. We obtain \begin{align*} \{123,124,125,134,135,145,234,235,245,345\}. \end{align*} Note, that each element in the set above follows the ordering $(\mathrm{smallest} < \mathrm{middle} < \mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from $\{1,2,3,4,5\}$ following the order $4<5$, i.e. $(\mathrm{smallest} < \mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(\mathrm{middle} < \mathrm{smallest} < \mathrm{largest})$.

We observe from (4), (5):

\begin{align*} |\mathcal{B}\star\mathcal{C}|=2\binom{5}{3}=2\cdot 10=20 \end{align*}

and the relationship with the generating functions $B(z)$ and $C(z)$ is given as \begin{align*} \color{blue}{A(z)}&=B(z)\cdot C(z)=\left(2\cdot \frac{z^3}{3!}\right)\cdot\left(\frac{z^2}{2!}\right)\\ &\,\,\color{blue}{=2\binom{5}{3}\frac{z^5}{5!}} \end{align*}

Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.