Classification of permutations

Definition: Type

Let . The type of is the partition of corresponding to the sizes of the Cycles Cycles of .

Definition: Conjugate permutations

Let . If there exists a permutation such that we say that and are conjugate.

Theorem

Let . Then and are conjugate if and only if they have the same type.

Proof:
: Let such that . We see that , meaning any -cycle of has a corresponding -cycle of which is just the image of on the cycle.
: We want to construct a such that . For each subset on which is a -cycle there is a corresponding on which is a -cycle. Let and . Then define for every . We then get that We see then that on is a bijection to , so when this is done for every and corresponding , we get a bijection which satisfies .

Definition: Transposition

A transposition is a permutation which only interchanges two elements, meaning it has only one -cycle and the rest -cycles.

We quickly see that any cycle can be written as a composition of transpositions, for example, . Since any permutation is the composition of cycles, any permutation is the composition of transpositions.

Notation

For any we denote the number of cycles of by .

Lemma

For any and transposition , is either or .

Proof:
We have two cases: either transposes elements in a single cycle of , or elements in different cycles of . In the first case, suppose we have a transposition of and , meaning we have since and , meaning . In the second case, suppose we have a transposition of and , meaning we have since and , meaning .

Theorem

Let be the composition of transpositions and also the composition of compositions. Then and have the same parity.

Proof:
Follows from Lemma Lemma since adding or removing from the total number of cycles must be done an even amount of times when going from the first composition of transpositions to the second, for the total number of cycles to be unchanged.

Definition: Even permutation, odd permutation

A permutation is even if it is the composition of an even number of transpositions, otherwise odd.

The sign of a permutation , denoted , is if it is odd, otherwise .

We notice that if can be written as transpositions and can be written as transpositions, then .

Theorem

For any integer exactly half of the permutations in are even and exactly half of them are odd.

Proof:
Let be all unique even permutations of . Then take any transposition . We see that are all odd, and that if , then , so they are all unique. Now for any odd we know is even, meaning for some , meaning , but so meaning every odd permutation is among .