Cycle Notation

discrete-math

Cycle Notation

The cycle notation describes the effect of repeatedly applying the permutation on the elements of the set $S$, with an orbit being called a cycle.

Given a cyclic permutation $\pi$:

By applying the permutation $\pi$ on an initial value $x$, $x$ will be eventually a successor by definition:

$$x=(\pi \circ \pi \circ \cdots \circ \pi )(x)$$

To represent this compactly, the cycle notation can be used:

$$(x\pi (x)\pi (\pi (x))\dots .)(y\dots )$$

Example: A a cyclic permutation that maps:

• $\pi :0\mapsto 1$,
• $\pi :1\mapsto 2$,
• $\pi :2\mapsto 1$, and
• $\pi :3\mapsto 3$

can be represented as:

$$\pi =(012)(3)$$