Next: Probability and Cycle Structure
Up: Background About Permutations and
Previous: Background About Permutations and
A permutation can also be written in a way that groups together the images of a given number
under repeated applications of .
For example, the permutation
can be written
The first group of numbers in parentheses indicates that 1 gets mapped to 3, 3 gets mapped to
4, 4 gets mapped to 7, and 7 gets mapped back to 1. Each of the other groupings is
interpreted in a similar way. These groups of numbers are called cycles, and this
notation for permutations is referred to as cycle notation. Following are several
facts relating to cycles and cycle notation.

A cycle of k numbers is referred to as a kcycle; for example, (1 3 4 7) is a 4cycle.

A cycle of one number indicates that the number is mapped to itself, and 1cycles are often
referred to as fixed points.

If a permutation
is applied k times, then the numbers in each kcycle in will return to their starting positions.

The number of times that a permutation
must be applied in order to return all
numbers to their starting positions is known as the order of ,
and will
equal the least common multiple of the lengths of all the cycles in .

It does not matter which number is written first in a cycle, as long as the order of the
numbers is preserved. For example, (1 3 4 7) = (4 7 1 3), but (1 3 4 7) (1 4 3 7)
Next: Probability and Cycle Structure
Up: Background About Permutations and
Previous: Background About Permutations and
20000925