Exercise 4.3.33 (Size of conjugacy classes in $S_n$)

Question

This exercise gives a formula for the size of each conjugacy class in $S_n$. Let $\sigma$ be a permutation in $S_n$ and let $m_1, m_2,\ldots,m_s$ be the {\bf distinct} integers which appear in the cycle type of $\sigma$ (including $1$-cycles). For each $i \in \{1,2,\ldots,s\}$ assume $\sigma$ has $k_i$ cycles of length $m_i$ (so that $\sum_{i=1}^s k_i m_i = n$). Prove that the number of conjugates of $\sigma$ is
$$\frac{n!}{(k_1! m_1^{k_1})\cdots (k_s! m_s^{k_s})}.$$
[ See Exercise 6 and 7 in Section 1.3 where this formula was given in some special cases.]

Richard Ganaye · Accepted Answer

\begin{proof} 
To build such a permutation, we start with any arrangement $(a_1,a_2,\ldots,a_n)$ of the integers $1,2,\ldots n$. The choice of such an arrangement can be made in $n!$ ways. Then we define $\sigma$ by taking $k_1$ cycles of length $m_1$, $k_2$ cycles of length $m_2$, $\ldots$, and $k_s$ cycles of length $m_s$.

For instance, if $(a_1, a_2,\ldots,a_{11}) = (2 ,7 , 3 ,11, 5, 10, 1,  4 ,8, 7, 9)$ and the cycle-type is $(1,1, 2,2,2, 3)$, then 
\begin{align*}
\sigma &= (2)(7) (3\ 11)(5\ 10) (1\ 4) (8\ 7 \ 9) \
&= (3\ 11)(5\ 10) (1\ 4) (8\ 7 \ 9).
\end{align*}
How many arrangements give the same permutation $\sigma$? For instance, in the example,
$$\sigma = (7)(2) (5\ 10)(11\ 3)(5\ 10) (1\ 4) (9\ 8\ 7).$$

For each index $i$, we can permute in any way the $k_i$ cycles of length $m_i$, in $k_i!$ ways, and any cycle of length $m_i$ in $m_i$ ways. Since there are $k_i$ such cycles, the numbers of possibilities is $m_i^{k_i}$. So the number of arrangements which give the same permutation is $(k_1! m_1^{k_1})\cdots (k_s! m_s^{k_s})$. This shows that
$$|{\mathcal O}_\sigma| = \frac{n!}{(k_1! m_1^{k_1})\cdots (k_s! m_s^{k_s})}.$$
\end{proof}

Exercise 4.3.33 (Size of conjugacy classes in $S_n$)

Answers

Comments

Exercise 4.3.33 (Size of conjugacy classes in $S_n$)

Answers

Comments

Add answer