Cycles and Fixed Points

Cycles And Fixed Points

In combinatorial mathematics, the cycles of a permutation π of a finite set S correspond bijectively to the orbits of the subgroup generated by π acting on S. These orbits are subsets of S that can be written as { c₁, ..., c_l }, such that

π(c_i) = c_{i + 1} for i = 1, ..., l − 1, and π(c_l) = c₁.

The corresponding cycle of is π written as ( c₁ c₂ ... c_n ); this expression is not unique since c₁ can be chosen to be any element of the orbit.

The size l of the orbit is called the length of the corresponding cycle; when l = 1, the cycle is called a fixed point. In counting the fixed points among the cycles of a permutation, the combinatorial notion of cycle differs from the group theoretical one, where a cycle is a permutation in itself, and its length cannot be 1 (even if that were allowed, this would not suffice to distinguish different fixed points, since any cycle of length 1 would be equal to the identity permutation).

A permutation is determined by giving an expression for each of its cycles, and one notation for permutations consist of writing such expressions one after another in some order. For example, let

be a permutation that maps 1 to 2, 6 to 8, etc. Then one may write

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) (7) = ...

Here 5 an 7 are fixed points of π, since π(5)=5 and π(7)=7. This kind of expression resembles the group-theoretic decomposition of a permutation as a product of cycles with disjoint orbits, but in that decomposition the fixed points do not appear.

There are different ways to write a permutation as a list of its cycles, but the number of cycles and their contents are given by the partition of S into orbits, and these are therefore the same for all such expressions.