The Order of a Permutation

With cycle notation, the order of a permutation can be read off with no multiplying at all.

Por qué funciona

Theorem. The order of a permutation written as a product of disjoint cycles of lengths $k_{1}, \dots, k_{r}$ is $\operatorname{lcm}(k_{1}, \dots, k_{r})$.
Proof. A $k$-cycle has order $k$: each application moves every entry one place around the cycle, and they all come back to the start for the first time after $k$ steps. Disjoint cycles commute, so $$(\gamma_{1}\gamma_{2}\cdots\gamma_{r})^{m} = \gamma_{1}^{m}\gamma_{2}^{m}\cdots\gamma_{r}^{m},$$ and since the cycles move different numbers, this is the identity exactly when each $\gamma_{i}^{m}$ is, that is, when every $k_{i}$ divides $m$. The least such $m$ is the lcm. $\square$

$(1\;2\;3)(4\;5)$: the 3-cycle returns after 3 steps and the 2-cycle after 2, so everything returns together after $\operatorname{lcm}(3, 2) = 6$ steps.

Ejemplo resuelto: Orders from cycle lengths

Find the orders of $(1\;2\;3)(4\;5)$, $(1\;2\;3\;4)(5\;6\;7\;8)$ and $(1\;2\;3\;4\;5)(6\;7\;8)$.

$\operatorname{lcm}(3, 2) = 6$.
$\operatorname{lcm}(4, 4) = 4$, not $8$ or $16$.
$\operatorname{lcm}(5, 3) = 15$.

Respuesta: $6$, $4$ and $15$.

Ejemplo resuelto: Overlapping cycles first

Find the order of $(1\;2)(2\;3)$.

The cycles overlap, so multiply first: $3 \to 2 \to 1$, $1 \to 1 \to 2$, $2 \to 3 \to 3$, giving $(1\;2\;3)$.
A single 3-cycle has order $3$.
(The lcm of the original lengths, $2$, would be wrong.)

Respuesta: Order $3$.

Cycle types and counting

The lengths of the disjoint cycles (with fixed points as cycles of length 1) form the cycle type. To count the permutations of a given type in $S_{n}$, fill the pattern with the $n$ numbers and divide out the repeats: each $k$-cycle can be written starting at any of its $k$ entries, and cycles of equal length can be listed in any order. With $m_{k}$ cycles of length $k$ (including $k = 1$): $$\#\{\text{permutations of that type}\} = \frac{n!}{\prod_{k} k^{m_{k}}\, m_{k}!}.$$

Ejemplo resuelto: Counting 3-cycles in $S_{5}$

How many 3-cycles does $S_{5}$ contain?

Fill $(\ast\;\ast\;\ast)$: $5 \cdot 4 \cdot 3 = 60$ ways.
Each 3-cycle is written $3$ ways (start anywhere).
$60/3 = 20$. The formula agrees: $5!/(3^{1} \cdot 1! \cdot 1^{2} \cdot 2!) = 120/6 = 20$.

Respuesta: $20$.

Ejemplo resuelto: A big power

Compute $\sigma^{100}$ for $\sigma = (1\;2\;3)(4\;5\;6\;7)$.

The order is $\operatorname{lcm}(3, 4) = 12$, so exponents work mod $12$: $100 = 12 \cdot 8 + 4$, and $\sigma^{100} = \sigma^{4}$.
Powers of disjoint cycles can be taken one cycle at a time: $(1\;2\;3)^{4} = (1\;2\;3)$ and $(4\;5\;6\;7)^{4} = e$.

Respuesta: $\sigma^{100} = (1\;2\;3)$.

Error común

Adding or multiplying cycle lengths instead of taking their lcm: $(1\;2\;3\;4)(5\;6)$ has order $\operatorname{lcm}(4, 2) = 4$, not $6$ or $8$. And take the lcm only after rewriting as disjoint cycles; overlapping ones can merge into longer cycles or cancel.

Idea clave

For disjoint cycles, the order of the product is the lcm of the cycle lengths. The cycle type also tells how many permutations look alike: $n!/\prod k^{m_{k}} m_{k}!$.

Cycle types and counting

Práctica

Se apoya en

Lleva a

Fuentes y lecturas