First, we consider the special case of a cycle of length 2, (*a*, *b*), which is a simple swap of two elements. Such a permutation is called a **transposition**. We already know that every permutation is a product of disjoint cycles. Furthermore, every cycle can be written as a product of transpositions:

(*a*_{1}, *a*_{2}, …, *a _{r}*) = (

*a*

_{1},

*a*

_{2})(

*a*

_{2},

*a*

_{3}) … (

*a*

_{r}_{-1},

*a*)

_{r}This means:

Every permutation can be written as a product of transpositions.

It is easy to see that this representation is far from unique. For instance, in degree 3, we already have (1, 2) = (1, 3)(2, 3)(1, 3). Nevertheless, we shall define the following.

A permutation is said to be

even(resp.odd) if it can be written as a product of an even (resp. odd) number of transpositions.

As the reader may suspect, a permutation cannot be both even and odd. The remainder of this post is devoted to the proof of this amazing result.

As a first observation, if we can write a permutation as a product of transpositions such that *r*+*s* is even, then we have:

But since it is a transposition. Hence, it suffices to prove this.

An

odd number of transpositions cannot compose to give the identity map.

The approach is to count the number of “crossed pairs”, i.e. let *σ* be the product of an odd number of *r *transpositions, and let *m* be the number of pairs of (*i*, *j*), *i* < *j*, such that *σ*(*i*) < *σ*(*j*). We claim that *m* and *r* have the same parity! To do this, we compare the number of crossings for these two permutations:

*σ* and *τ* := *σ* (a, b).

Note that most of the time *σ*(*i*) = *τ*(i) and trouble only occurs when *i* = *a* or *i* = *b*, i.e. the following three cases:

- (
*i*,*j*) = (*a*,*b*) : this (*i*,*j*) is a crossed pair for*σ*if and only if it is not a crossed pair of*τ*; *i*=*a*, but*j*≠*a*,*b*: a crossed pair is a negative value of (*i*–*j*)(*σ*(*i*) –*σ*(*j*)), so to compute the parity of the number of crossed pairs, we take the product of all these terms and look at the sign:

for *σ *: ;

for *τ* : .

*i*=*b*, but*j*≠*a*,*b*: now we take the products:

for *σ *: ;

for *τ* : .

Thus, the product for both *σ *and *τ* is:

which are equal (and not just possess the same sign)! This completes our proof.

The following result follows straight from the definition:

The product of two permutations of the same parity is even.

The product of two permutations of different parity is odd.

*Example* : What is the permutation of the riffle-shuffle in Section I.3?

*Answer* : The permutation is given by (2, 6, 8, 9, 5, 3)(4, 7). We use the above recipe to convert cycle to product of transpositions: (2, 6, 8, 9, 5, 3) = (2, 6)(6, 8)(8, 9)(9, 5)(5, 3). Since the permutation is a product of 5 + 1 = 6 permutations, it is *even.*

[ Incidentally, one sees from this proof, that a cycle is odd (*resp*. even) if and only if it has even (*resp*. odd) length. ]