Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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

2 Answers 2

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\geq$2} \\ 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}}$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.