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

  • 1
    $\begingroup$ 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 $$[1]\leftrightarrow[2]\qquad(3)\leftrightarrow(4)$$ and $$[3]\leftrightarrow[4]\qquad(1)\leftrightarrow(2)$$ separately, which should not happen as they represent the same permutation. $\endgroup$ – Sangchul Lee Apr 19 '19 at 21:12

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


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)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.