Dtyjlui

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}^nbinom{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_kfrac{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^ncolor{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,bulletbullet,bulletbulletbullet,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,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ 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,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
begin{align*}
A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
=left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain 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^3right)timesleft(z^1+z^2right)=(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}^nbinom{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)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
begin{align*}
color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
end{align*}
which is defined as:

• The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar 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}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
&=left({123}star{45}right)cupleft({213}star{45}right)\
&={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
&qquadcup{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}starmathcal{C}|=2binom{5}{3}=2cdot 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(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
&,,color{blue}{=2binom{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.