0
$\begingroup$

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!

$\endgroup$
1
  • 2
    $\begingroup$ You should formulate more carefully. Generating functions don't have cycles, you are probably thinking about generating functions for permutations with given parity of their number of cycles. Which by the way corresponds bijectively (for fixed $n$) to their own parity. $\endgroup$ May 22, 2013 at 7:34

3 Answers 3

2
$\begingroup$

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}) . $$

$\endgroup$
2
$\begingroup$

[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.

$\endgroup$
6
  • $\begingroup$ There aren't any odd permutations of $n$ for $n<2$. $\endgroup$ May 22, 2013 at 7:36
  • $\begingroup$ @Marc: You're right of course :-) Corrected. $\endgroup$
    – joriki
    May 22, 2013 at 8:02
  • $\begingroup$ Can you give me a specific example of such bijection? $\endgroup$
    – Geeeee
    May 22, 2013 at 10:28
  • $\begingroup$ @Geeeee: I'm not sure I understand the question. The bijection is given by (left or right, you can use either) multiplication by a fixed transposition, so an example is given by any example of a transposition, e.g. $(12)$. $\endgroup$
    – joriki
    May 22, 2013 at 13:52
  • $\begingroup$ @joriki: I mean the example of a bijection that shows: there are as many permutations with an even number of cycles as those with an odd number of cycles. $\endgroup$
    – Geeeee
    May 22, 2013 at 14:36
0
$\begingroup$

For the sake of completeness and because it is a powerful construct let us recall the combinatorial class of permutations enumerated by cycles which is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times\textsc{CYC}(\mathcal{Z}))$$

This immediately gives the bivariate generating functions of permutations by cycles, which is $$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$ Now if we only want an even number of cycles we take $$\frac{1}{2} G(z, 1) + \frac{1}{2} G(z, -1)$$ which works out to $$\frac{1}{2} \exp\left(+1\times\log\frac{1}{1-z}\right) + \frac{1}{2} \exp\left(-1\times\log\frac{1}{1-z}\right)$$ which simplifies to $$\frac{1}{2}\frac{1}{1-z} + \frac{1}{2} (1-z).$$ Similarly for an odd number of cycles we take $$\frac{1}{2} G(z, 1) - \frac{1}{2} G(z, -1)$$ which works out to $$\frac{1}{2} \exp\left(+1\times\log\frac{1}{1-z}\right) - \frac{1}{2} \exp\left(-1\times\log\frac{1}{1-z}\right)$$ which simplifies to $$\frac{1}{2}\frac{1}{1-z} - \frac{1}{2} (1-z).$$ The generating function $G(z,u)$ and its cousins yield a large variety of statistics of permutations and their cycles and that is why I mention it here.

$\endgroup$
2
  • $\begingroup$ Can you explain how you arrive at $\frac{1}{2}G(z,1)+\frac{1}{2}G(z,-1)$? I don't understand why we set $u=1$ and $u=-1$, add the two terms and then dividie by $2$. Thanks! $\endgroup$
    – user826130
    Apr 28, 2021 at 16:00
  • $\begingroup$ We have $((+1)^n + (-1)^n)/2$ equal to one if $n$ is even and zero if $n$ is odd. $\endgroup$ Apr 29, 2021 at 15:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .