10.4 Product Structures

Let $M$ be a combinatorial structure of interest, say permutations, derangements, number of fixed points et al. Let $M(x)$ be the EGF for sequence $m_k$ which is the number of combinatorial structures $M$ in set $[k].$ For example, if $M=\mathrm{\Pi }$, permutations then $\mathrm{\Pi }(x)={\sum }_{n=1}{x}^n={(1-x)}^{-1}$. For $M=S$, the number of ways to divide the set into singletons, trivially $s_k=1$ and $S(x)=e^x$. Say $P$ denotes partition into pairs, then $p(n)=0$ for $n$ odd. For $n=2k$, choose a pair $x_1$ for $1$ and then pair the remaining $2k-2$ points. So $p(2k)=(2k-1)p(2k-2)$ and hence $p(2k)=(2k-1)(2k-3)\mathrm{\dots }1=:(2k-1)!!$. So

$$P(x)=\sum _{k=0}(2k-1)!!\frac{x^{2k}}{(2k)!}=\sum _{k=0}\frac{{(x^2/2)}^k}{k!}=e^{x^2/2}.$$

If a structure $M$ can be uniquely split into a structure $A$ and structure $B$ then we say $M=A.B$. In this case

$$M(x)=\sum _{n=0}^{\mathrm{\infty }}(\sum _{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)a_k{b}_{n-k})\frac{x^n}{n!}.=A(x)B(x).$$