# The size of a conjugacy class in the symmetric group

I'm trying to prove the formula for the size of a conjugacy class in $$S_n$$. here is my try,

Suppose the permutation whose conjugacy class size is to be found has a number of $$k_i$$ cycles of lengths $$m_i$$ where $$i$$ is between one and some integer $$s$$ in its cycle decomposition.My idea is to fill in the places of the cycles one by one in a manner that guarantees that every integer appear only once.To that end, I find all possible ways to form sets of lengths $$m_i$$ from the original set of $$n$$ integers, and the number of these ways is (taking into account that numbers in a cycle may change order and therefore change the permutation) $$\frac{n!}{\left(n-m_i\right)!\ m_i}$$ and once the first place is filled I have to ensure that the second cycle has completely different numbers so the number of $$m_i$$ cycles that may be put in the second place and that have different numbers is $$\frac{\left(n-m_i\right)!}{\left(n-2m_i\right)!\ m_i}$$ and so I proceed in this manner until all the places are filled

once I find all possible ways to fill in every place the problem is equivalent to finding the number of possible ways to choose one element from each one of a certain number of sets (that are disjoint) and the number of ways is the product of possible choices . and skipping a lot of computation I find the final answer to be $$\frac{n!}{\prod_{i=1}^s\left(m_i^{k_i}\right)}$$ which is wrong

Most explanations on the web say that we must divide by $$k_i!$$ because the order in which the cycles are present doesn't matter but I think I've taken that into account the way I did it and still how does that imply that we must divide by the product of $$k_i$$ factorials? this is a big skip that I wouldn't do if I didn't have a systematic way to justify doing it. However, I'm probably wrong

please be as detailed as possible in your answer because I looked for explanations on the web but they all skip many details and I don't seem to be able to justify a lot of these skips

• For example, let $n = 4$ and say you are interested in finding the conjugacy class of the permutations having two 2-cycles. It seems that you want to fill in numbers to $$\square\leftrightarrow\square\qquad\bigcirc\leftrightarrow\bigcirc.$$ Now it seems to me that your argument counts $$\leftrightarrow\qquad(3)\leftrightarrow(4)$$ and $$\leftrightarrow\qquad(1)\leftrightarrow(2)$$ separately, which should not happen as they represent the same permutation. – Sangchul Lee Apr 19 at 21:12

Here's an example, with $$n=10$$, you can generalize it.

$$(1,2,3)(4,5,6)(7,8)(9,10)$$

For each of the $$10!$$ orderings, consider the relabeling with the cycles in the same order $$3,3,2,2$$. For example,

$$(4,2,5),(6,8,7)(10,3)(1,9)$$ corresponding to the ordering $$4,2,5,6,8,7,10,3,1,9$$

The only question is how many of these orderings give the same permutation. There are two issues.

1) The two $$3$$-cycles can be ordered in $$2! = 2$$ ways to give the same permutation e.g. $$(6,8,7),(4,2,5)(10,3)(1,9)$$

The two $$2$$-cycles can be ordered in $$2! = 2$$ ways to give the same permutation e.g. $$(4,2,5),(6,8,7)(1,9,)(10,3)$$

2) WITHIN each $$k$$-cycle, there are $$k$$ orderings that denote the same cycle. For our example that's a factor of $$3*3*2*2$$ separate from re-ordering whole cycles as in (1).

The overall factor $$2!*2!*3*3*2*2$$ is the number of relabelings of the original permutation which leave it unchanged as a permutation -- i.e. the number of permutations that conjugate it to itself, i.e. the number of permutations that commute with it.

So there are $$10!/(2!*2!*3*3*2*2)$$ distinct conjugates of $$(1,2,3)(4,5,6)(7,8)(9,10)$$