8
$\begingroup$

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, for example using exponential generating functions.

Is there a simple bijective proof?

Remark: The June 2009 edition of Ponder This sketches a proof by Eytan Sayag but I have not succeeded in understanding it. Perhaps all that is needed is for someone to explain that proof to me in more detail.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ It seems that there is a product formula in each case: The number of permutations with all cycles of odd length, or of even length, on $2n$ elements is $(1 \cdot 3 \cdot 5 \cdots \cdot (2n-1))^2$; the number of permutations with all cycles of odd length on $2n+1$ elements is $(1 \cdot 3 \cdot 5 \cdots \cdot (2n-1))^2 (2n+1)$. Do we have proofs of these formulae? $\endgroup$
    – David E Speyer
    May 19, 2015 at 17:54
  • 1
    $\begingroup$ In the even case, $1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2n-1)$ is also the number of fixed-point-free involutions, so one could also ask for a bijection between pairs of such involutions and constant-parity permutations of each kind. $\endgroup$
    – Noam D. Elkies
    May 19, 2015 at 18:27
  • $\begingroup$ @DavidSpeyer: When you say "proofs," do you mean "bijective proofs"? The formulae follow immediately by generatingfunctionology. $\endgroup$
    – Timothy Chow
    May 19, 2015 at 20:41
  • $\begingroup$ Yes, I mean bijective. $\endgroup$
    – David E Speyer
    May 19, 2015 at 20:43
  • 1
    $\begingroup$ @MartinRubey Yes, this works to biject pairs of fixed-point-free-involutions with all-even-permutations. More precisely, you need a rule for how to turn a red-blue coloring of an unoriented $2k$ cycle into an orientation of that $2k$ cycle. There is no particularly natural choice but, for example, you could choose to oriented such that the red edge incident to the largest entry in the cycle is oriented away from that entry. Dealing with the all-odd case this way seems harder, though. $\endgroup$
    – David E Speyer
    May 19, 2015 at 23:56

3 Answers 3

Reset to default
14
$\begingroup$

Yes, and the original paper is the following.

MR1774748 Reviewed Bóna, Miklós; McLennan, Andrew; White, Dennis Permutations with roots. Random Structures Algorithms 17 (2000), no. 2, 157–167.

Improve this answer
$\endgroup$
15
$\begingroup$

Here is Eytan's proof in more detail. First, there is a canonical way to write the cycle decomposition of a permutation. You order the cycles in descending order based on the largest member they contain, then you order each individual cycle to start with this largest member. An example of a permutation written in this canonical form is

$$(614)(523).$$

Given such a permutation in which all cycles have odd length and $n$ is even, there must be an even number of such cycles, so we can pair them up and then have one of the cycles give up a member to one of the other cycles. Let's do this by moving the last member of the second cycle to the end of the first cycle, so for example

$$(614)(523) \to (6143)(52).$$

Note that the result stays in canonical form. The inverse of this transformation is as follows: go through each of the even cycles and compare their last members to the first (biggest) members of the next cycle. If it's bigger, it gets split off into its own odd cycle of length $1$, and the two are paired up as above. If it's smaller, it gets tacked onto the end of the next cycle, and the two are paired up as above.

Improve this answer
$\endgroup$
8
  • $\begingroup$ how do you know all the evens go to odds or vice versa? $\endgroup$
    – JMP
    May 19, 2015 at 19:22
  • $\begingroup$ because the classic bijection is en.wikipedia.org/wiki/…, and yours looks nothing like it:-) $\endgroup$
    – JMP
    May 19, 2015 at 19:30
  • 6
    $\begingroup$ @JonMarkPerry Your Wikipedia link and Qiaochu are talking about very different things. Wikipedia is bijecting partitions, he is bijecting permutations. $\endgroup$
    – David E Speyer
    May 19, 2015 at 20:42
  • 1
    $\begingroup$ @Jon: I don't understand that comment. I've provided an explicit bijection: the map from all-odd-cycles to all-even-cycles is described in the second paragraph, and its inverse is described in the third paragraph. $\endgroup$
    – Qiaochu Yuan
    May 20, 2015 at 5:44
  • 1
    $\begingroup$ I'm not sure what Jon's objection is either, but I know that one thing I tripped over when reading Eytan's proof at first was that I'm accustomed to arranging the cycles in increasing order of the largest element (because then you can erase the parentheses and still know which permutation you're talking about). That's what Jon's phrase "classic bijection" reminds me of. But in this proof, the parentheses are not erased, so it's O.K. to arrange them in decreasing order of the largest element. $\endgroup$
    – Timothy Chow
    May 20, 2015 at 21:55
6
$\begingroup$

There is a very readable bijective proof of this fact in Miklós Bóna's book Walk Through Combinatorics.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.