Next: Combining Permutations Up: Permutations Previous: Two Row Notation

## Cycle Notation

Write the example above like this:

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:

is

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 is not a valid form. As we will see in the next section, something like can be reduced to a valid form--in this particular case to .

As a final example, consider this permutation of :

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:

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

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:

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

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