TAOCP 1.3.3 Exercise 16

Section 1.3.3: Applications to Permutations

Exercise 16. [M15] Start with the permutation 1324 in linear notation; convert it to canonical cycle form and then remove the parentheses; repeat this process until arriving at the original permutation. What permutations occur during this process?

Verified: yes
Solve time: 32m02s

Solution

Let the initial permutation in linear notation be $1324$. This means the mapping on ${1,2,3,4}$ is

$$ 1 \mapsto 1,\quad 2 \mapsto 3,\quad 3 \mapsto 2,\quad 4 \mapsto 4. $$

The cycle containing $2$ is obtained by iterating the mapping: $2 \mapsto 3$ and $3 \mapsto 2$, hence $(2,3)$. The elements $1$ and $4$ are fixed, giving singleton cycles $(1)$ and $(4)$. Thus the canonical cycle form is

$$ (1)(2,3)(4), $$

which reduces, by the convention that singleton cycles are omitted, to

$$ (2,3). $$

Removing parentheses yields the linear notation obtained by writing the images of $1,2,3,4$ under this permutation. From $(2,3)$, one has $1 \mapsto 1$, $2 \mapsto 3$, $3 \mapsto 2$, $4 \mapsto 4$, hence the linear notation is again

$$ 1324. $$

Applying the same conversion again produces the same cycle decomposition $(2,3)$ and therefore the same linear notation $1324$. The transformation is idempotent because both representations describe the same permutation on ${1,2,3,4}$ and each conversion step reconstructs that permutation exactly.

Thus every iteration of the procedure yields the same permutation, so the sequence of permutations is constant.

This completes the solution. ∎

$$ \boxed{1324} $$