I'm looking to find the number of permutations of [n] for which all cycles have even length, call that number $f_n$.
I've seen here: Number of permutations of a specific cycle decomposition that the exponential generating function is given by:
$G_1(z) = \exp\left( \sum_{k\ge 1} \frac{z^{2k}}{2k} \right) = \sqrt{ \frac{1}{1-z^2}} = \frac{\sqrt{1-z^2}}{1-z^2}$
Does anyone have an explanation for why we have this egf?
More generally, the exponential generating function for permutations with cycle lengths in some set $S$ is
$$ \exp\left(\sum_{k\in S}\frac{z^k}k\right)\;. $$
This is because there are $(k-1)!$ different labeled cycles of length $k$, so the exponential generating function for the number of admissible cycles is
$$ \sum_{k\in S}\frac{(k-1)!}{k!}z^k=\sum_{k\in S}\frac{z^k}k\;. $$
Why going from cycles to permutations consisting of cycles corresponds to exponentiating the exponential generating function is explained at Wikipedia here and here.
