next up previous
Next: Combining Permutations Up: Permutations Previous: Two Row Notation

Cycle Notation

Write the example above like this:

\begin{displaymath}(1 4 3) \end{displaymath}

This indicates that the contents of box 1 moves to box 4, the contents of box 4 to box 3, and the contents of box 3 back moves back into box 1. The system is called ``cycle notation'' since the contents of the boxes in parentheses move in a cycle: 1 to 4, 4 to 3, and 3 back to 1.

Some permutations have more than one cycle. For example, the cycle notation for the permutation corresponding to:

\begin{displaymath}\Big(
\begin{array}{cccc}
1 & 2 & 3 & 4 \\
3 & 4 & 1 & 2
\end{array}\Big) \end{displaymath}

is

\begin{displaymath}(1 3)(2 4). \end{displaymath}

There are two ``cycles''. 1 moves to 3 and 3 moves back to 1. At the same time, 2 moves to 4, and 4 back to 2. In other words, the contents of boxes 1 and 3 are cycled, and at the same time, the contents of boxes 2 and 4 are cycled.

In cycle notation, there cannot be any duplicate elements in the various cycles that make up the permutation, so something like $(1 3)(1 2)$ is not a valid form. As we will see in the next section, something like $(1 3)(1 2)$ can be reduced to a valid form--in this particular case to $(1 3 2)$.

As a final example, consider this permutation of $\{1, 2, 3, 4, 5, 6, 7, 8 \}$:

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

It moves the ball in box 1 to box 3, 3 to 5, and 5 back to 1. At the same time, it moves 2 to 7, 7 to 6, 6 to 8, and 8 back to 1. Notice that 4 is not involved, so it stays fixed. If you want to make it clear that 4 is a member of the set of items under consideration, but that in this particular permutation it is not moved, you can write:

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

In fact, the special permutation that does not move anything is often written as: $(1)$.

Note also that the ordering doesn't matter as long as each item to be permuted appears only once, and that you can list a cycle beginning with any member of it. All of the following indicate exactly the same permutation:

$(1 3 5)(2 7 6 8)$ $(2 7 6 8)(1 3 5)$ $(7 6 8 2)(1 3 5)$
$(3 5 1)(6 8 2 7)$ $(8 2 7 6)(5 1 3)$ $(6 8 2 7)(5 1 3)$

In the rest of this document, we'll use the cycle notation.


next up previous
Next: Combining Permutations Up: Permutations Previous: Two Row Notation
Zvezdelina Stankova-Frenkel 2000-10-04