# Permutations with all cycles odd length and permutations with all cycles even length

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.

• 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? – David E Speyer May 19 '15 at 17:54
• 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. – Noam D. Elkies May 19 '15 at 18:27
• @DavidSpeyer: When you say "proofs," do you mean "bijective proofs"? The formulae follow immediately by generatingfunctionology. – Timothy Chow May 19 '15 at 20:41
• Yes, I mean bijective. – David E Speyer May 19 '15 at 20:43
• @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. – David E Speyer May 19 '15 at 23:56

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.

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.

• how do you know all the evens go to odds or vice versa? – JonMark Perry May 19 '15 at 19:22
• because the classic bijection is en.wikipedia.org/wiki/…, and yours looks nothing like it:-) – JonMark Perry May 19 '15 at 19:30
• @JonMarkPerry Your Wikipedia link and Qiaochu are talking about very different things. Wikipedia is bijecting partitions, he is bijecting permutations. – David E Speyer May 19 '15 at 20:42
• except for he's not actually bijecting anything, @DavidSpeyer – JonMark Perry May 19 '15 at 20:56
• @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. – Qiaochu Yuan May 20 '15 at 5:44

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