TAOCP 1.3.3 Exercise 4

Exercise 4. [10] Express $(abd)(ef)(acf)(bd)$ as a product of disjoint cycles.

Verified: yes
Solve time: 2m50s

Corrected Solution to Exercise 1.3.3.4 (4)

We are asked to express

$$ (abd)(ef)(acf)(bd) $$

as a product of disjoint cycles, using Knuth's left-to-right convention for composition of permutations.

1. Image of $a$:

$$ a \xrightarrow{(abd)} b \xrightarrow{(ef)} b \xrightarrow{(acf)} b \xrightarrow{(bd)} d $$

So $a \mapsto d$.

2. Image of $d$:

$$ d \xrightarrow{(abd)} a \xrightarrow{(ef)} a \xrightarrow{(acf)} c \xrightarrow{(bd)} c $$

So $d \mapsto c$.

3. Image of $c$:

$$ c \xrightarrow{(abd)} c \xrightarrow{(ef)} c \xrightarrow{(acf)} f \xrightarrow{(bd)} f $$

So $c \mapsto f$.

4. Image of $f$:

$$ f \xrightarrow{(abd)} f \xrightarrow{(ef)} e \xrightarrow{(acf)} e \xrightarrow{(bd)} e $$

So $f \mapsto e$.

5. Image of $e$:

$$ e \xrightarrow{(abd)} e \xrightarrow{(ef)} f \xrightarrow{(acf)} a \xrightarrow{(bd)} a $$

So $e \mapsto a$.

6. Image of $b$:

$$ b \xrightarrow{(abd)} d \xrightarrow{(ef)} d \xrightarrow{(acf)} d \xrightarrow{(bd)} b $$

So $b \mapsto b$ and is fixed.

Following the mapping chain for elements that are not fixed:

$$ a \mapsto d \mapsto c \mapsto f \mapsto e \mapsto a $$

This produces the 5-cycle

$$ (adcfe) $$

The element $b$ is fixed, so it does not appear in the cycle notation by convention.

The disjoint-cycle decomposition of

$$ (abd)(ef)(acf)(bd) $$

$$ \boxed{(adcfe)}. $$

This computation correctly accounts for the left-to-right application of the cycles.