next up previous
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 $\sigma$. For example, the permutation

\begin{displaymath}\sigma = \pmatrix{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\cr
3 & 6 & 4 & 7 & 5 & 9 & 1 & 8 & 2\cr}
\end{displaymath}

can be written

\begin{displaymath}\sigma = (1\ 3\ 4\ 7)(2\ 6\ 9)(5)(8).
\end{displaymath}

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.