Next: Order of a permutation Up: Permutations Previous: Stirling numbers of the   Contents

## Transpositions and shuffles

A transposition is a permutation which swaps two points and fixes the rest.

Theorem 5.6.7   Every permutation is the product of transpositions.

Proof. Since every permutations is the product of cycles we only need to check for cycles. This is easy: .

Theorem 5.6.8   For a given permutation , the number of transpositions used to write as their product is either always even or always odd.

We write . We say that is an
 even odd
permutation. Let be the number of cycles in the disjoint cycle representation of (including fixed points).

Lemma 5.6.9   If is a transposition that .

Proof. If and are in the same cycle of then has two cycles, so . If and are in different cycles then they contract them together and .

Proof. [Proof of theorem 6.8] Assume . Then . Hence as required.

We note that , thus and thus is a homomorphism from to . A -cycle is an even permutation iff is odd. A permutation is an
 even odd
permutation iff the number of even length cycles in the disjoint cycle representation is
 even odd
.

Next: Order of a permutation Up: Permutations Previous: Stirling numbers of the   Contents
root 2002-06-10