# conjugacy classes in the symmetric group $S_{n}$

We start by providing an alternate proof that in $S_{n}$, every permutation has a cycle decomposition, and we prove that the cycle decomposition is essentially unique.

###### Theorem 1.

Every permutation in $S_{n}$ has a cycle decomposition that is unique up to ordering of the cycles and up to a cyclic permutation of the elements within each cycle.

###### Proof.

We construct the cycle decomposition for $\sigma\in S_{n}$. Let $X=\{1,\ldots,n\}$, and regard $\sigma$ as acting on $X$. Let $G=\langle\sigma\rangle$ be the subgroup of $S_{n}$ generated by $\sigma$. Then $G$ acts on $X$, so by the orbit-stabilizer theorem, it partitions $X$ into a unique set of orbits. In addition, for any orbit $Gx$, we have that

 $\sigma^{i}x\leftrightarrow\sigma^{i}G_{x}$

is a bijection, where $G_{x}$ is the stabilizer of $x$ in $G$.

Now, $G=\langle\sigma\rangle$ is cyclic and thus $G/G_{x}$ is cyclic as well; its order is the smallest power $d$ of $\sigma$ such that $\sigma^{d}\in G_{x}$. Note also that $d=\lvert Gx\rvert=[G:G_{x}]$. Using the explicit bijection above, we see that the unique cosets of $G_{x}$ in $G$ are

 $G_{x},\sigma G_{x},\ldots,\sigma^{d-1}G_{x}$

and that the elements of $Gx$ are

 $x,\sigma x,\ldots,\sigma^{d-1}x$

Thus on any orbit of size $d$, $\sigma$ is a $d$-cycle. This shows that a cycle decomposition exists.

Uniqueness now follows easily, since the cycle determined by $\sigma$ on an element of order $d$ is determined uniquely by construction from the element. Choosing a different element in the same orbit, say $\sigma^{j}x$, gives instead

 $\sigma^{j}x,\sigma^{j+1}x,\ldots,\sigma^{d-1}x,x,\sigma x,\ldots,\sigma^{j-1}x$

which is the same cycle permuted left by $j$ . ∎

We can thus write

###### Definition 1.

If $\sigma\in S_{n}$ and $\sigma$ is written as the product of the disjoint cycles of lengths $n_{1},\ldots,n_{k}$ with $n_{i}\leq n_{i+1}$ for each $i, then $n_{1},\ldots,n_{k}$ is the cycle type of $\sigma$.

The above theorem proves that the cycle type is well-defined.

###### Theorem 2.

Two permutations $\sigma,\tau\in S_{n}$ are conjugate if and only if they have the same cycle type.

###### Proof.

Assume first that $\sigma$ and $\tau$ are conjugate; say $\tau=\sigma_{1}\sigma\sigma_{1}^{-1}$. Write $\sigma$ as a product of disjoint cycles

 $(\alpha_{1}\ldots\alpha_{a})(\beta_{1}\ldots\beta_{b})(\ldots)$

To show that $\sigma$ and $\tau$ have the same cycle type, it clearly suffices to show that if $j$ follows $i$ in the cycle decomposition of $\sigma$, then $\sigma_{1}(j)$ follows $\sigma_{1}(i)$ in the cycle decomposition of $\tau$. But suppose $\sigma(i)=j$. Then

 $\tau(\sigma_{1}(i))=\sigma_{1}\sigma\sigma_{1}^{-1}(\sigma_{1}(i))=\sigma_{1}% \sigma(i)=\sigma_{1}(j)$

and we are done.

Now suppose $\sigma$ and $\tau$ have the same cycle type. Write the cycle decomposition for each permutation in such a way that the cycles are listed in nondecreasing order of their length (including cycles of length 1). We then have (for example)

 $\displaystyle\sigma$ $\displaystyle=(a_{1})(a_{2}a_{3}a_{4})(a_{5}\ldots a_{n})$ $\displaystyle\tau$ $\displaystyle=(b_{1})(b_{2}b_{3}b_{4})(b_{5}\ldots b_{n})$

Define $\sigma_{1}$ to be the permutation that takes $a_{i}$ to $b_{i}$. Clearly $\sigma\in S_{n}$, since each of $1,\ldots,n$ appears exactly once among the $a_{i}$ and once among the $b_{i}$. But also, since the cycle types of $\sigma$ and $\tau$ match, we see that

 $\sigma_{1}\sigma\sigma_{1}^{-1}(b_{i})=\sigma_{1}\sigma(a_{i})=\sigma_{1}(a_{j% })=b_{j}$

where $a_{j}$, $b_{j}$ are the ”‘next”’ elements in their respective cycles. Thus $\tau=\sigma_{1}\sigma\sigma_{1}^{-1}$ and we are done. ∎

###### Corollary 3.

The number of conjugacy classes in $S_{n}$ is the number of partitions of $n$.

###### Proof.

Each distinct cycle type in $S_{n}$ represents a distinct partition of $n$, and each cycle type represents a conjugacy class. The result follows. ∎

We can give an explicit for the size of each conjugacy class in $S_{n}$.

###### Theorem 4.

Suppose $\sigma\in S_{n}$, and let $m_{1},m_{2},\ldots m_{r}$ be the distinct integers (including $1$ if applicable) in the cycle type of $\sigma$, and let there be $k_{i}$ cycles of order $m_{i}$ in $\sigma$. (Thus $\sum k_{i}m_{i}=n$). Then the number of conjugates of $\sigma$ is exactly

 $\frac{n!}{(k_{1}!m_{1}^{k_{1}})(k_{2}!m_{2}^{k_{2}})\cdots(k_{r}!m_{r}^{k_{r}})}$
###### Proof.

The size of a conjugacy class is the number of cycles of the given cycle type. Choose a cycle type, and order the cycles in some order. Consider the $n!$ possible assignments of the integers from $1$ to $n$ into the ”‘holes”’ in the cycles. Call two such arrangements equivalent if they define the same permutation. It is clear that this is an equivalence relation, and that the relation partitions the arrangements. We will determine the size of each equivalence class.

Consider a particular arrangement (i.e. permutation), and consider the $k_{i}$ cycles of order $m_{i}$ in that permutation. Each of the cycles can be written in $m_{i}$ different ways (by starting with a different element). Also, the cycles themselves can appear in any of $k_{i}!$ possible orders while still representing the same permutation. Thus if, for example, $k_{i}=2$ and the first cycle contains $a_{1},\ldots a_{l}$ while the second contains $b_{1},\ldots,b_{l}$, that is the same permutation as if the first cycle contained $b_{1},\ldots,b_{l}$ and the second contained $a_{1},\ldots,a_{l}$. So there are $k_{i}!m_{i}^{k_{i}}$ equivalent permutations considering the cycles of order $m_{i}$. So the total number of permutations, considering each of the possible cycle orders, equivalent to the given permutation is

 $(k_{1}!m_{1}^{k_{1}})(k_{2}!m_{2}^{k_{2}})\ldots(k_{r}!m_{r}^{k_{r}})$

and the result follows. ∎

For example, let $n=5$ and let’s compute the size of the conjugacy class containing the permutation $(2~{}3)(4~{}5)$. In this case, $r=2$,

 $\displaystyle m_{1}=1$ $\displaystyle,\quad k_{1}=1$ $\displaystyle m_{2}=2$ $\displaystyle,\quad k_{2}=2$

and the skeleton for the permutation is

 $(\cdot)(\cdot~{}\cdot)(\cdot~{}\cdot)$

There are $5!=120$ ways of placing $1,2,3,4,5$ into this skeleton. However, given a particular choice, say $(2)(1~{}3)(4~{}5)$, the first $2$-cycle may be written as $(1~{}3)$ or as $(3~{}1)$, while the second may be written as either $(4~{}5)$ or $(5~{}4)$. In addition, either pair can appear first ($k_{2}=2$). The number of choices for ways to represent the $2$-cycles is thus $2!\cdot 2^{2}=8$. The formula in the theorem indeed predicts that there are $5!/(2!\cdot 2^{2})=120/8=15$ permutations with this cycle type; in fact, they are (omitting the trivial $1$-cycles):

 $(1~{}2)(3~{}4)$ $(1~{}2)(3~{}5)$ $(1~{}2)(4~{}5)$ $(1~{}3)(4~{}5)$ $(2~{}3)(4~{}5)$ $(1~{}3)(2~{}4)$ $(1~{}3)(2~{}5)$ $(1~{}4)(2~{}5)$ $(1~{}4)(3~{}5)$ $(2~{}4)(3~{}5)$ $(1~{}4)(2~{}3)$ $(1~{}5)(2~{}3)$ $(1~{}5)(2~{}4)$ $(1~{}5)(3~{}4)$ $(2~{}5)(3~{}4)$

## References

• 1 D.S. Dummitt, R.M. Foote, Abstract Algebra, Wiley, 2004.
Title conjugacy classes in the symmetric group $S_{n}$ ConjugacyClassesInTheSymmetricGroupSn 2013-03-22 17:16:24 2013-03-22 17:16:24 rm50 (10146) rm50 (10146) 8 rm50 (10146) Topic msc 20B05 msc 20B30 cycle type