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