# Create a Generating function

Let $P$ be the set of permutations all of whose cycles are of even length. Prove that the exponential generating function for $P$ is $\dfrac{1}{\sqrt{1-x^2}}$.

-
What have you done? Where did it go wrong? What other generating functions have you seen? What have you tried? – mixedmath Apr 12 '13 at 15:47

A bit of notation to make the answer clearer. I shall write $P_n$ to be the set of all partitions of the set $\{1,\ldots,n\}$ and $\sigma=\{S_1,\ldots,S_k\} \in P_n$ to mean that $\sigma$ is a partition of the set $\{1,\ldots,n\}$ into "parts" $S_1,\ldots,S_k$

Define $$a_n= \begin{cases} (n-1)! & \text{if n is even and n\geq2} \\ 0 & \text{otherwise} \end{cases}$$ and $b_n=1$ for all $n$. Let $A(x)=\sum\limits_{i=0}^\infty\frac{a_nx^n}{n!}$ and $B(x)=\sum\limits_{n=0}^\infty\frac{a_nx^n}{n!}$. Then the exponential generating series for $P$ is $B(A(x))=\sum\limits_{n=0}^\infty\frac{c_nx^n}{n!}$, where

$$c_n=\sum\limits_{\sigma=\{S_1,\ldots,S_k\} \in P_n}b_k a_{|S_1|}a_{|S_2|}\cdots a_{|S_k|}=\sum\limits_{\sigma=\{S_1,\ldots,S_k\} \in P_n,\ |S_i|\text{ even}}(|S_1|-1)! \cdots (|S_k|-1)!,$$

which is exactly the number of permutations of the set $\{1, \ldots,n\}$ with all cycles even!

Note that $B(x)=\exp(x)$ and

$$A(x)=\sum\limits_{n \geq 2,\text{ even}}^\infty \frac{(n-1)!x^n}{n!}=\sum\limits_{n \geq 2,\text{ even}}^\infty\frac{x^n}{n}=\frac{1}{2}(\ln(1+x) - \ln(1-x))= \ln \left(\frac{1}{\sqrt{1-x^2}}\right),$$

Hence the generating function for $P$ is $B(A(x))=\exp\left(\ln \left(\frac{1}{\sqrt{1-x^2}}\right)\right)=\dfrac{1}{\sqrt{1-x^2}}$

-

This is definitely straightforward using symbolic combinatorics as formalized by Flajolet and Sedgewick. Let $\mathcal{Q}$ be the combinatorial class of permutations consisting only of even cycles.

We have the combinatorial specification $$\mathcal{Q} = \mathfrak{P}(\mathfrak{C}_2(\mathcal{Z}) + \mathfrak{C}_4(\mathcal{Z}) + \mathfrak{C}_6(\mathcal{Z}) + \cdots)$$ where $\mathcal{Z}$ is the singleton class.

Translating this into generating functions we obtain for the required EGF $G(z)$ that $$G(z) = \exp\left(\frac{z^2}{2} + \frac{z^4}{4} + \frac{z^6}{6}+\cdots\right) = \exp \left(\frac{1}{2}\left(\frac{(z^2)}{1} + \frac{(z^2)^2}{2} + \frac{(z^2)^3}{3} +\cdots\right)\right) \\= \exp\left(\frac{1}{2} \log \frac{1}{1-z^2}\right) = \left(\frac{1}{1-z^2}\right)^{1/2} = \frac{1}{\sqrt{1-z^2}}.$$

-