= Solution
For a <permutation> $\sigma$ of a finite set, start with a point $x$. Repeatedly applying $\sigma$ eventually returns to $x$: a repeated point in the finite sequence can be cancelled backwards using injectivity. The distinct successive points before that return form a cycle. If any point has not yet been used, repeat the construction there. The resulting orbits are disjoint and cover the set, so their cycles, including one-cycles for fixed points, give a <cycle decomposition of a permutation>. Disjoint cycles commute because they act on different points.
Conjugation relabels a cycle:
$$
\gamma(x_1\ x_2\ \cdots\ x_n)\gamma^{-1}
=(\gamma x_1\ \gamma x_2\ \cdots\ \gamma x_n).
$$
Thus conjugate <permutations> have the same <cycle type>. Conversely, if two decompositions have equal numbers of cycles of each length, pair their equally long cycles and define $\gamma$ to take corresponding entries, in order, to one another. Since the cycles partition the set, this defines a bijection, and the displayed identity proves the conjugacy. Hence \b[cycle type characterizes conjugacy in the symmetric <group>].
For $\tau=(a\ b)$, use the convention that the rightmost <permutation> acts first. If $a,b$ are in different cycles, write those cycles as
$$
(a\ x_1\ldots x_p)(b\ y_1\ldots y_q).
$$
Left multiplication by $\tau$ changes the arrow into $a$ to an arrow into $b$, and the arrow into $b$ to an arrow into $a$. Following these arrows gives the single cycle
$$
(a\ x_1\ldots x_p\ b\ y_1\ldots y_q).
$$
No other cycles change, so $\ell(\tau\sigma)=\ell(\sigma)-1$. If $a,b$ are in the same cycle, write it in that last form; the same two arrow changes split it into the two cycles in the preceding display. Thus $\ell(\tau\sigma)=\ell(\sigma)+1$. Empty lists are allowed and produce one-cycles. This proves <transposition changes the cycle count by one> in all cases:
$$
\boxed{\ell(\tau\sigma)=\ell(\sigma)\pm1.}
$$
Back to article page
