exponential generating functions containing an even/odd number of cycles

Question

How to derive the exponential generating functions that having an even/odd number of cycles? And how to define a bijection between them? Is there any example of this? Thanks in advance!

Answer 1

[Edit: corrected the silly mistake pointed out by Marc]

The parity of the number of cycles of a permutation corresponds to the parity of the permutation itself. For $n\gt1$ a bijection is given by multiplying every even permutation by a fixed transposition. Thus there are $n!/2$ permutations of each kind. This doesn't work for $n\le1$ since in this case there's no transposition to multiply by. There's one permutation with an even number ($0)$ of cycles for $n=0$ and one permutation with an odd number ($1$) of cycles for $n=1$, so the exponential generating functions are

$$ 1+\sum_{n=2}^\infty\frac12x^n=1+\frac12\left(\sum_{n=0}^\infty x^n-1-x\right)=\frac12\left(1-x+\frac1{1-x}\right) $$

for an even number of cycles and

$$ x+\sum_{n=2}^\infty\frac12x^n=x+\frac12\left(\sum_{n=0}^\infty x^n-1-x\right)=\frac12\left(-1+x+\frac1{1-x}\right) $$

for an odd number of cycles.

Answer 2

Minor correction to the answer by joriki, If you are counting permutations with an even number of cycles, then there is one for $n=0$ but not for $n=1$, and for odd number of cycles it is the opposite. Therefore for the even number of cycles you get $$ \frac12(1-x+\frac1{1-x}) = \frac12\times\frac{2-2x+x^2}{1-x} =1+\frac12(\frac{x^2}{1-x}), $$ and for odd numbers of cycles you get similarly $$ \frac12(-1+x+\frac1{1-x}) = \frac12\times\frac{2x-x^2}{1-x} =x+\frac12(\frac{x^2}{1-x}) . $$