Bijection between permutations of even length cycles and pairs of factors

Question

I was trying to solve Exercise 3.13.15 in Cameron's Combinatorics: Topics, Techniques, Algorithms. It goes like this:

(a) Let $n = 2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a partition of $X$ into $k$ sets of size $2$. Show that the number of factors is equal to $(2k-1)!!=1.3.5...(2k-1)$.

(b) Show that a permutation of $X$ interchanges some $k$-subset with its complement if and only if all its cycles have even length. Prove that the number of such permutations is $((2k - 1)!!)^2$. [HINT: any pair of factors defines a partition of $X$ into a disjoint union of cycles, and conversely. The correspondence is not one-to-one, but the non-bijectiveness exactly balances.]

I was able to solve the first part, but I am stuck in the second part. Specifically, I don't understand the hint: how can two factors define a partition of $X$ into a disjoint union of cycles? Can anyone shed some light on it? Somehow one should be able to show that this defines a bijection, which implies the claimed number of permutations.

Answer 1

Let $E$ be the set of permutations of $X$ where all cycles have even length. Let $F$ be the set of ordered pairs $(f_1,f_2)$, where $f_1,f_2$ are both factors of $X$. I will define a bijection $\phi:E\to F$, with inverse $\psi:F\to E$, which proves that $|E|=|F|$. It should be clear that $|F|=(2k-1)!!$, completing the proof.

Given $\pi \in E$, let $(\sigma_1,\dots,\sigma_{2r})$ be a particular cycle of $\pi$. To be unambiguous, assume that $\sigma_1$ is the smallest element of $\{\sigma_1,\dots,\sigma_{2r}\}$. There are two cases:

• If $r=1$, then $\{\sigma_1,\sigma_2\}$ will be a pair in both $f_1$ and $f_2$.

• If $r\ge 2$, then the pairs $\{\{\sigma_1,\sigma_2\},\dots,\{\sigma_{2i-1},\sigma_{2i}\},\dots,\{\sigma_{2r-1},\sigma_{2r}\}\}$ will all occur in $f_1$, while the pairs $\{\{\sigma_2,\sigma_3\},\dots\{\sigma_{2r},\sigma_{2r+1}\},\dots,\{\sigma_{2r},\sigma_1\}\}$ will occur in $f_2$.

Repeating this for all cycles in $\pi$, both $f_1$ and $f_2$ will be factors. The pair of factors $(f_1,f_2)$ defined this way is the image $\phi(\pi)$.

Conversely, given factors $(f_1,f_2)$ on $X$, imagine a multi-graph with vertex set $X$ with exactly $2k$ edges, one edge for each pair occurring in $f_1$ or $f_2$. This is multigraph, because there could be some doubled edges, which occurs when $f_1$ and $f_2$ have a pair in common. This is a $2$-regular multigraph, so it can be partitioned into cycles. Furthermore, each cycle has a unique orientation, defined by saying that the smallest element $m$ of each cycle is succeeded in the orientation by the partner of $m$ in $f_1$. Furthermore, each cycle has even length, because a cycle must alternate between using edges from $f_1$ and $f_2$.

It is easy (and maybe a bit tedious) to verify that $\phi$ and $\psi$ are mutual inverses to each other.

Answer 2

The hint isn't needed to establish the first sentence of part (b). For that, consider the case where all cycles of a given permutation have even length; within each cycle, color the elements "red" and "blue" (however you like) in alternating fashion. It is then clear that the permutation takes the red set to the blue set and vice versa. Conversely, if the permutation swaps a $k$-element "red" set with a $k$-element "blue" set, then the same is evidently true within each cycle of the permutation: the cycle takes red elements to blue ones and vice versa. Therefore each cycle must be of even length.

That you found the hint mysterious is completely understandable. I did too at first. But the basic idea should be this: given a permutation $\sigma: X \to X$ all of whose cycles have even length, draw an arrow from $x$ to $\sigma(x)$ for every $x \in X$, then pick a representative element in each cycle, and color the arrows alternately red and blue (say you color each arrow out of a representative element red). The red arrows give you a bipartite graph, from a subset $X_1$ of $k$ elements of all $2k$ elements of $X$, to its complementary subset $X_2$, also with $k$ elements. The blue arrows do the same, giving a bipartite graph from $X_2$ to $X_1$. These bipartite graphs are really the same as factors, and this gives you the correspondence. Notice that the permutation can be recovered from the pair of bipartite graphs.

There's a different way to calculate the number of permutations on a $2k$-element set all of whose cycles have even length, using egfs (exponential generating functions) $\sum_{n \geq 0} a_n x^n/n!$. The egf $g(x)$ whose coefficients $a_n$ count the number of necklaces or cycle structures of even length greater than zero is

$$\frac{x^2}{2} + \frac{x^4}{4} + \frac{x^6}{6} + \ldots = \frac1{2} \log(1 - x^2)$$ and then the coefficients of

$$\exp(g(x)) = (1 - x^2)^{1/2}$$

count the number of ways of decomposing a set into parts, each of which has an even necklace structure. Via the cycle decomposition, this is exactly what we are trying to count. But the coefficients $b_n$ of

$$\sum_{n \geq 0} \frac{b_n x^n}{n!} = (1 - x^2)^{1/2}$$

are $b_{2n} = [(2n-1)!!]^2$ (else $0$), as is easily seen from the binomial expansion, and this gives a second way of establishing the second part of (b).