8

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.

Timothy Chow
  • 78,129
  • 2
    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
  • 1
    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
  • @DavidSpeyer Colour the arcs of the permutation (as a digraph) blue and red? – Martin Rubey May 19 '15 at 22:01
  • 1
    @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

3 Answers3

15

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.

Qiaochu Yuan
  • 114,941
  • how do you know all the evens go to odds or vice versa? – JMP May 19 '15 at 19:22
  • because the classic bijection is http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Odd_parts_and_distinct_parts, and yours looks nothing like it:-) – JMP May 19 '15 at 19:30
  • 6
    @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 – JMP May 19 '15 at 20:56
  • @Jon: both directions of the bijection cause every cycle to change in size by $\pm 1$, which sends odd cycles to even cycles and vice versa. And as David says, this is a different argument from the argument about partitions. – Qiaochu Yuan May 20 '15 at 05:21
  • you've only proved a bijection exists, which we, as your Q states, already know. what is needed is an explicit bijection (so that other people can follow the argument with no doubts) – JMP May 20 '15 at 05:43
  • 1
    @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 05:44
  • 1
    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. – Timothy Chow May 20 '15 at 21:55
14

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.

Miklos Bona
  • 156
6

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

Vince Vatter
  • 2,329