How many 2m-permutations, consisting only of cycles of even length?

Question

How many 2m-permutations, consisting only of cycles of even length?

I have found this formula: $$Q_2(n) =((2n − 1)!!)^2$$ but how it can be proven?

Answer 1

Suppose we want to construct such a permutation $\pi$ of $1,\ldots, 2m$. Note that $\pi(1)$ must not be $1$, otherwise there would be a $1$-cycle. So arbitrarily pick $x \in \{2,\ldots, 2m\}$ to be $\pi(1)$. There are $2m-1$ possible choices. Now if we take a permutation of $\{1,\ldots,2m\} \backslash \{1,x\}$ having only even cycles, expressed in disjoint cycle notation, and insert $1,x$ in one of those cycles following any element, we get a permutation of $\{1,\ldots, 2m\}$ with only even cycles. Alternatively, we can insert $(1,x)$ as a cycle on its own. All the allowable permutations of $\{1,\ldots,2m\}$ are obtained in this way, because if you take such a permutation where $x$ follows $1$ and erase $1$ and $x$ you obtain a permutation of $\{1,\ldots,2m\} \backslash \{1,x\}$ with only even cycles. Thus we get the recursion

$$Q_2(m) = (2m-1) ((2m-2)+1) Q_2(m-1) = (2m-1)^2 Q_2(m-1)$$ with initial condition $Q_2(1) = 1$. The rest is induction.

Answer 2

The combinatorial species of permutations consisting only of even cycles is given by $$\mathfrak{P}(\mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \mathfrak{C}_{=6}(\mathcal{Z})+ \mathfrak{C}_{=8}(\mathcal{Z}) + \cdots).$$

This translates to the generating function $$G(z) = \exp\left(\frac{z^2}{2} + \frac{z^4}{4} + \frac{z^6}{6} + \frac{z^8}{8} + \cdots\right)$$ which is $$\exp\left(\frac{1}{2}\left(\frac{z^2}{1} + \frac{z^4}{2} + \frac{z^6}{3} + \frac{z^8}{4} + \cdots\right)\right)$$ or $$\exp\left(\frac{1}{2}\log\frac{1}{1-z^2}\right) = \sqrt{\frac{1}{1-z^2}}.$$

By the Newton binomial we thus have the closed form for $n=2m$ $$(2m)! [z^{2m}] \sqrt{\frac{1}{1-z^2}} = ((2m-1)!!)^2.$$

This is OEIS A001818.

Remark. The coefficient extraction can be performed by Lagrange inversion. We have $$[z^{2m}] G(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m+1}} \sqrt{\frac{1}{1-z^2}} \; dz.$$ This is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(z^2)^{m+1}} \sqrt{\frac{1}{1-z^2}} \; z \; dz.$$

Put $1-z^2 = u^2 $ so that $- z \; dz = u\; du$ to get $$- \frac{1}{2\pi i} \int_{|u-1|=\epsilon} \frac{1}{(1-u^2)^{m+1}} \frac{1}{u} \times u \; du \\ = - \frac{1}{2\pi i} \int_{|u-1|=\epsilon} \frac{1}{(1-u)^{m+1}} \frac{1}{(1+u)^{m+1}} \; du \\ = (-1)^m \frac{1}{2\pi i} \int_{|u-1|=\epsilon} \frac{1}{(u-1)^{m+1}} \frac{1}{(2+u-1)^{m+1}} \; du \\ = \frac{(-1)^m}{2^m} \frac{1}{2\pi i} \int_{|u-1|=\epsilon} \frac{1}{(u-1)^{m+1}} \frac{1}{(1+(u-1)/2)^{m+1}} \; du \\ = \frac{(-1)^m}{2^m} \frac{1}{2\pi i} \int_{|u-1|=\epsilon} \frac{1}{(u-1)^{m+1}} \sum_{q\ge 0} {q+m\choose m} (-1)^q \frac{(u-1)^q}{2^q} \; du \\ = \frac{(-1)^m}{2^m} {2m\choose m} \frac{(-1)^m}{2^m} = \frac{1}{2^{2m}} {2m\choose m}.$$ It follows that the answer is given by $$(2m)! \times \frac{1}{2^{2m}} {2m\choose m}.$$

This implies that $$\frac{Q_2(m)}{Q_2(m-1)} = (2m)(2m-1) \frac{1}{2^2} \frac{(2m)(2m-1)}{m\times m} = (2m-1)^2$$ as pointed out by Robert Israel.