Number of permutations with all cycles of even length

Question

For even $n$ (only!), let $e_n$ stand for the number of permutations with all cycle of even length. Let $E(x)$ be the exponential generating functions. Prove that $E(x) = (1 - x^2)^{-\frac12}.$

I tried to find the generating function as a formal sum, but it didn't work out.

Answer 1

The egf for the number of ways to put $n$ elements into an even length cycle is \begin{align} \sum_{n=1}^\infty (2n-1)!\frac{x^{2n}}{(2n)!} &=\frac{x^2}{2}+\frac{x^4}{4}+\frac{x^6}{6}+\dots \\&=\frac12(-\log(1-x)-\log(1+x)) \\&=\log\big((1-x^2)^{-1/2}\big). \end{align} The second equality follows from $\log(1+x)=x-x^2/2+x^3/3-x^4/4+\dots$

A permutation with only even cycles is formed by partitioning $\{1,2,\dots,n\}$ into disjoint nonempty components and turning each part into an even length cycle. Therefore, by the exponential formula, the egf for even cycle only permutations is $$ \exp\log\big((1-x^2)^{-1/2}\big)=(1-x^2)^{-1/2} $$

Answer 2

We attempt to find a recurrence relation for the $e_n$, and convert that to information about the exponential generating function $E(x)=\sum_n e_n\frac{x^n}{n!}$.

Sort the permutations of $n$ with all cycles of even length by the length of the cycle that includes $1$. If this cycle has length $2k$, then there are $\binom{n-1}{2k-1}$ ways to choose the other $2k-1$ elements in the cycle, $(2k-1)!$ different cycles on those $2k$ elements, and $e_{n-2k}$ permutations of the $n-2k$ elements outside that cycle with all cycles of even length. Therefore, $$e_n = \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n-1}{2k-1}\cdot (2k-1)!\cdot e_{n-2k} = \sum_{k=1}^{\lfloor n/2\rfloor}\frac{(n-1)!}{(n-2k)!}\cdot e_{n-2k}$$ $$n\frac{e_n}{n!} =\sum_{k=1}^{\lfloor n/2\rfloor}\frac{e_{n-2k}}{(n-2k)!}$$ Now, multiply by powers of $x$ to convert that to a generating function. We have that $xE'(x)=\sum_n ne_n\frac{x^n\cdot x}{n!}$, so \begin{align*}n\frac{e_n}{n!}x^n &= \sum_{k=1}^{\lfloor n/2\rfloor}\frac{e_{n-2k}x^{n-2k}}{(n-2k)!}\cdot x^{2k}\\ xE'(x) &= E(x)\cdot (x^2+x^4+\cdots) = \frac{x^2}{1-x^2}E(x)\\ \frac{E'(x)}{E(x)} &= \frac{x}{1-x^2}\\ \ln(E(x)) &= \int \frac{x}{1-x^2}\,dx = C-\frac12\ln(1-x^2)\\ E(x) &= A(1-x^2)^{-\frac12}\end{align*} We can lock down the constant of integration by evaluating at $x=0$; $e_0=1$, so $E(0)=1$ and $A=1$. There it is.

Answer 3

We want to enumerate $\,e_n,\,$ the number of permutations in $\,S_n\,$ with all cycles of even length. We note that in such a case, $\,n\,$ must be even also since the it is the sum of the length of all of the cycles. One idea comes from OEIS sequence A001818 which is the number of permutations in $\,S_{2n}\,$ with all cycles of even length and also permutations with all cycles of odd length. Note that OEIS sequence A177145 is our sequence $\,e_n\,$ except its offset is $1$ instead of $0$.

Every permutation in $\,S_n\,$ uniquely determines a bi-partition into elements that belong to even length cycles and those that belong to odd length cycles. The e.g.f. is $\,(1-x)^{-1/2}(1+x)^{-1/2}\,$ for even length cycles and $\,(1-x)^{-1/2}(1+x)^{1/2}\,$ for the rest. Their product is $\,(1-x)^{-1} = \sum_{n=0}^\infty n!\, x^n/n!\,$ which is the e.g.f. of $\,n!,\,$ the number of all permutations in $\,S_n\,$ as it should be.

Now apply this to the case of permutations in $\,S_{2n}.\,$ Again, each such permutation uniquely determines a bi-partition of its elements into even and odd cycles. We assume that the e.g.f. of permutations in $\,S_{2n}\,$ with all cycles of even length is $\,f(x)\,$ and also those of all odd length. Their product is $\,f(x)^2\,$ which must equal $\,(1-x^2)^{-1}\,$ which is the e.g.f. of the number of all permutations in $\,S_{2n}.\,$ This implies that $\,f(x) = (1-x^2)^{-1/2} = \sum_{n=0}^\infty \,(2n-1)!!^2\, x^{2n}/(2n)!\,$ as requested.

One proof that $\,f(x)\,$ is also the e.g.f. of permutations with all cycles of odd length is combinatorial. Given a permutation in $\,S_n\,$ pick any element $\,t\,$ which is a fixed point or not. If it is, then the rest of the elements form a permutation with all cycles of odd length as before. If $\,t\,$ is not a fixed point, then it is mapped to a second element and mapped from a third element. If these two other elements are removed, the remaining permutation has all cycles of odd length as before.