Cycle type of a permutation
Contents
Definition
Let be a finite set and
be a permutation. The cycle type of
is the data of how many cycles of each length are present in the cycle decomposition of
. There are two typical ways of specifying the cycle type.
The definition also applies for infinite sets; here, we also need to include cycles of infinite length, i.e., the chains.
Definition as an unordered list of cycle sizes
The cycle type of a permutation is defined as the unordered list of the sizes of the cycles in the cycle decomposition of . For instance, consider the permutation with cycle decomposition:
This permutation has cycle type . Since this is an unordered list, this can also be written as
or
.
Note that the sum of all the cycle sizes must equal the size of the whole set . Thus, the cycle type of a permutation is an unordered integer partition of the size of the set.
Definition as information of how many cycles of each length there are
This decsribes the cycle type as an ordered sequence where
is the number of cycles of size (length)
. Thus, the permutation:
has and
.
Note that give the cycle type in either form, it can be converted to the other form.
Facts
- Cycle type determines conjugacy class: Two permutations are conjugate in the symmetric group if and only if they have the same cycle type. In particular, this means that the set of conjugacy classes in the symmetric group on a finite set is in bijection with the set of unordered integer partitions of the size of the set.