I was working towards proving $A_5$ is the only nontrivial normal subgroup of $S_5$. To do this, I wanted to find a set of representatives of conjugacy classes of $S_5$, and their respective orders.
With some research, I found that $1, (12), (123), (12)(34), (1234), (12)(345), (12345)$ are a set of representatives, with orders $1,10,20,15,30,20,24$. What is the most efficient way to determine something like this by hand, without taking an element $\sigma$, conjugating it by all $120$ elements of $S_5$, and then doing it again with a new element which wasn't in the orbit of $\sigma$ until the set is exhausted?
Best Answer
Consider the effect of conjugation on cycles. Given the cycle $c=(a_1~a_2~\cdots~a_k)$ and $\sigma\in S_n$, the permutation $\sigma c\sigma^{-1}$ maps $\sigma(a_i)$ to $\sigma(a_{i+1})$ (cycle the index modulo $k$), and all other arguments are fixed by the permutation. Hence
$$c^\sigma=\sigma(a_1~a_2~\cdots~a_k)\sigma^{-1}=(\sigma (a_1)~\sigma(a_2)~\cdots~\sigma(a_k)).$$
If $c_1,\cdots,c_l$ are disjoint cycles, $\sigma(c_1\cdots c_l)\sigma^{-1}=(\sigma c_1\sigma^{-1})\cdots(\sigma c_l\sigma^{-1})$, hence conjugation preserves not only cycles and cycle lengths, but cycle types as well. Moreover, conjugation acts transitively on permutations of a given cycle type. Suppose $\pi=c_1\cdots c_l$ and $\rho=d_1\cdots d_l$ are two permutations and their disjoint cycle decompositions such that each $c_i$ and $d_i$ have the same length.
We construct a $\sigma$ in pieces: if $c_i=(a_1~a_2~\cdots~a_k)$ and $d_i=(b_1~b_2~\cdots~b_k)$ (note $k$ can vary with $i$), let $\sigma$ send $a_j\mapsto b_j$ for $j=1,2,\cdots,k$. After doing this for each cycle (even the ones of length one, which are normally left out of written representations for efficiency), we will have that $\sigma \pi \sigma^{-1}=\rho$, by having equivalent cycle decompositions. This $\sigma$ is not unique; we could rewrite $c_i$ cycled by $1$ in index as $(a_k~a_1~\cdots~a_{k-1})$ and $\sigma$ would turn out different.
Cycle types are in bijection with integer partitions. For $n=5$, we have
$$\begin{array}{c | c}\lambda\vdash5 & \sigma \\ \hline (5) & (1~2~3~4~5) \\ (4,1) & (1~2~3~4)(5) \\ (3,2) & (1~2~3)(4~5) \\ (3,1,1) & (1~2~3)(4)(5) \\ (2,2,1) & (1~2)(3~4)(5) \\ (2,1,1,1) & (1~2)(3)(4)(5) \\ (1,1,1,1,1) & (1)(2)(3)(4)(5) \end{array}$$
On the left are integer partitions of $5$, and on the right are easily constructed representatives (in cycle notation) of the conjugacy class - cycle type - associated to the partition.