Cycle type of a permutation

From Groupprops
Jump to: navigation, search

Definition

Let S be a finite set and \sigma:S \to S be a permutation. The cycle type of \sigma is the data of how many cycles of each length are present in the cycle decomposition of \sigma. 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 \sigma. For instance, consider the permutation with cycle decomposition:

(1,3,5)(2,4)(6)(7,8)

This permutation has cycle type (3,2,1,2). Since this is an unordered list, this can also be written as (1,2,2,3) or (1,2,3,2).

Note that the sum of all the cycle sizes must equal the size of the whole set S. 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 i_1, i_2, i_3, \dots where i_j is the number of cycles of size (length) j. Thus, the permutation:

(1,3,5)(2,4)(6)(7,8)

has i_1 = 1, i_2 = 2, i_3 = 1 and i_j = 0, j \ge 4.

Note that give the cycle type in either form, it can be converted to the other form.

Facts