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}}$.
Tell me more
×
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.
|
|
|||||
|
|
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}}$ |
||||
|
|
|
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}}.$$ |
|||
|
|
