# Combinatorial proof of Recurrence for the number of permutations of odd order

Let $a_n$ denote the number of permutations of odd order in $S_n$. This is sequence A000246 in OEIS. Then there is the recurrence relation on OEIS that $a_{2n} = (2n-1)a_{2n-1}$ and $a_{2n+1} = (2n+1)a_{2n}$, or equivalently $a_n = a_{n-1} + (n-1)(n-2)a_{n-2}$.

It seems like there should be a combinatorial proof for this result.

Since there isn't a simple recurrence for the number of partitions with odd parts, it doesn't seem like working on the level of partitions will work.

$a_n-a_{n-1}$ is the number of odd order permutations in $S_n$ that move $1$. These permutations look like $(1\, i\,j\,\cdots)\cdots$ where the first cycle has odd length $\ge3$. The number of these is $(n-1)(n-2)t$ where $t$ is the number of odd order permutations $(1\, 2\,3\,\cdots)\cdots$. But these correspond to odd order permutations $(3\,\cdots)\cdots$ of the numbers $3$ to $n$. There are $a_{n-2}$ of these, and this proves your final recurrence.

These permutations are precisely the ones that do not contain even cycles, giving the species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=5}(\mathcal{Z}) + \mathfrak{C}_{=7}(\mathcal{Z}) + \cdots)$$

This yields the EGF

$$G(z) = \exp\left(\sum_{q\ge 1} \frac{z^q}{q} - \sum_{q\ge 1} \frac{z^{2q}}{2q}\right) \\ = \exp\log\frac{1}{1-z} \exp\left(- \frac{1}{2} \log\frac{1}{1-z^2}\right) \\ = \frac{\sqrt{1-z^2}}{1-z}.$$

Differentiate to obtain

$$G'(z) = \frac{\sqrt{1-z^2}}{1-z} \frac{1}{1-z} - \frac{\sqrt{1-z^2}}{1-z} \frac{z}{1-z^2} = G(z) \frac{1}{1-z^2}.$$

Extracting coefficients we find for $n\ge 2$

$$n! [z^n] G'(z) (1-z^2) = n! [z^n] G(z) \quad\text{or}\quad a_{n+1} - n! [z^{n-2}] G'(z) = a_n$$

which finally yields

$$a_{n+1} = a_n + n! \times \frac{a_{n-1}}{(n-2)!} \quad\text{or}\quad a_{n+1} = a_n + n (n-1) a_{n-1}$$

as desired.

For the second recurrence we start with the closed form from the EGF

$$n! \sum_{q=0}^{\lfloor n/2\rfloor} [z^{2q}] \sqrt{1-z^2} = n! \sum_{q=0}^{\lfloor n/2\rfloor} (-1)^q {1/2\choose q}.$$

Since $\lfloor (2n+1)/2\rfloor = \lfloor 2n/2\rfloor$ we have

$$a_{2n+1} = (2n+1) a_{2n}$$ by inspection.

The first recurrence now yields

$$a_{2n+1} = a_{2n} + 2n (2n-1) a_{2n-1} \quad\text{or}\quad (2n+1) a_{2n} = a_{2n} + 2n (2n-1) a_{2n-1}$$

and finally

$$2n a_{2n} = 2n (2n-1) a_{2n-1} \quad\text{or}\quad a_{2n} = (2n-1) a_{2n-1}.$$