Next: Probability and Cycle Structure Up: Background About Permutations and Previous: Background About Permutations and

## Cycles and Cycle Structure

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 k-cycle; for example, (1 3 4 7) is a 4-cycle.
• A cycle of one number indicates that the number is mapped to itself, and 1-cycles are often referred to as fixed points.
• If a permutation is applied k times, then the numbers in each k-cycle 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

2000-09-25