I’m preparing a talk about representations of the symmetric group so I’ll write up some of it on this blog.

Recall that every permutation $\pi \in S_n$ can be uniquely decomposed (modulo the order of the cycles) in a product of disjoint cycles. i.e.

$\pi = (i_{11} \cdots i_{1j_1})(i_{21} \cdots i_{2j_2}) \cdots (i_{m1} \cdots i_{mj_m})$

for some $m$, where $\sum_{k=1}^{m}j_k = n$. Here for example the cycle $(1234)$ represents the permutation of the set $\{1,2,3,4\}$ that takes 1 to 2, 2 to 3, 3 to 4 and 4 to 1. If $(i_1 \cdots i_j)$ is some cycle of a permutation in $S_n$ and $\sigma \in S_n$, then

$\tau := \sigma (i_1 \cdots i_j) \sigma^{-1} = (\sigma(i_1) \cdots \sigma(i_j))$.

Indeed, let $k \in \{ 1, \ldots, n \}$. If $k = \sigma(i_l)$ for some $1 \leq l \leq j$, then $\tau(k) = \sigma(i_{l+1})$. If not, i.e. if $\sigma^{-1}(k) \notin \{ i_1, \ldots, i_j \}$, then $\tau(k) = \sigma \sigma^{-1}(k) = k$.

So for some $\pi \in S_n$ with its decomposition in cycles as above, we have, for $\sigma \in S_n$,

$\sigma \pi \sigma^{-1} = \sigma(i_{11} \cdots i_{1j_1}) \sigma^{-1} \sigma (i_{21} \cdots i_{2j_2}) \sigma^{-1} \cdots \sigma (i_{m1} \cdots i_{mj_m}) \sigma^{-1}$

$= (\sigma(i_{11}) \cdots \sigma(i_{1j_1})) \cdots (\sigma(i_{m1}) \cdots \sigma(i_{mj_m}))$.

This shows that the number of $k-$cycles $(1 \leq k \leq n)$ in the cycle decomposition of $\pi \in S_n$ is preserved under conjugation. Conversely, if $\pi$ and $\pi'$ have the same number of $k-$cycles for all $1 \leq k \leq n$ in their cycle decomposition, there is an obvious permutation $\sigma \in S_n$ such that $\pi' = \sigma \pi \sigma^{-1}$. What we get from this is the fact that the “cycle type” completely determines the conjugacy classes in $S_n$.

For a positive integer $n \in \mathbb{N}$, a partition of $n$ is an ordered set of integers $\lambda = \lambda_1 \geq \lambda_2 \geq \cdots \lambda_k$ such that $\sum_{i=1}^k \lambda_k = n$. The notation $\lambda \vdash n$ indicates that $\lambda$ is a partition of $n$.

For example, $3 \geq 2 \geq 2 \geq 1 \geq 1 \geq 1 \geq 1$ is a partition of $11$. One way to compactify the notation would be to write this partition as $32^21^4$.

There is an obvious bijective correspondence between cycle types of permutations in $S_n$ and partitions of $n$: to the permutation $(i_{11} \cdots i_{1j_1}) \cdots (i_{m_1} \cdots i_{mj_m})$ is associated the partition $\lambda = j_1, \ldots, j_m$. The conjugacy classes of $S_n$ are thus indexed by the partitions of $n$.

The function $p(n)$ that associates to a positive integer $n$ the number of partitions of $n$ has been extensively studied. There is no known closed form for this but according to Wikipedia, Hardy & Ramanujan obtained in 1918 an asymptotic formula for $p(n)$ as $n \rightarrow \infty$:

$p(n) \sim \dfrac{1}{4n\sqrt{3}} \text{exp} \left( \pi \sqrt{ \dfrac{2n}{3}} \right)$.

By an easy counting argument, we find that for a given partition $\lambda = 1^{k_1} \cdots n^{k_n}$ of $n$, the number of elements of $S_n$ in the associated conjugacy class is

$\dfrac{n!}{\displaystyle\prod_{j=1}^n (k_j)! j^{k_j}}$.