Past exam of the mathematics course of the University of Oxford / 2023 / Prelims / Mathematics I / 7 / a (Cycle structure)

Conjugating a cycle simply relabels its entries. With permutations composed from right to left,This follows by applying each side to $\rho (a_j)$ and to points outside the displayed cycle. Consequently conjugation preserves the lengths in the disjoint cycle decomposition, including fixed points, and therefore preserves cycle type.

Conversely, suppose two permutations have the same cycle type. Pair their cycles of equal length, including their one-cycles. Define a bijection $\rho$ by mapping the entries of each cycle of the first permutation, in their cyclic order, to the entries of the paired cycle of the second. Because the cycles partition $\{1,\dots ,n\}$, these assignments combine into a permutation. The displayed identity then conjugates the first permutation to the second. Thus they are conjugate group elements exactly when their cycle types agree.

Let the lengths in the disjoint cycle decomposition of $\tau$ be ${\ell }_1,\dots ,{\ell }_s$, with fixed points contributing length one. Disjoint cycles commute, and ${\tau }^m=e$ if and only if every cycle raised to $m$ is the identity, equivalently ${\ell }_j$ divides $m$ for every $j$. Hence the order of a group element isIn particular, the identity has order one.

For $0\le k\le \lfloor n/2\rfloor$, first select an ordered list of $2k$ distinct entries. There are $n!/(n-2k)!$ lists. Pair consecutive entries to obtainEach product of $k$ disjoint transpositions is counted $2^{k}k!$ times: each pair has two orientations, and the $k$ pairs can be ordered in $k!$ ways. There is no other duplication, by uniqueness of the disjoint cycle decomposition. ThereforeIf $2k>n$, there are no such permutations. For $k=0$, $T_0=\{e\}$.

For distinct $i,j\ne 1$, direct conjugation givesThus the given star transpositions generate every transposition. Every cycle can in turn be expressed asBy the disjoint cycle decomposition, every permutation is a product of cycles, hence of transpositions, hence of the given star transpositions. ThereforeFor $n=1$, the empty generating set of a group generates the trivial group $S_1$.