<s>[INST] 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. 
 [/INST] 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}.$$
</s>