Number of conjugacy classes in permutation group $ S_n $ for some n.

Question

I was asked to find out the number of conjugacy classes in the permutation group $ S_6 $.It is 11.But for large n it is difficult to find out .so I want to know is there any way to find out the number of conjugacy classes for large n?

Answer 1

A conjugacy class in $S_n$ is determined by the length of its cycles. That's a partition of $n$. The partition numbers (OEIS link) are well-studied. There's a fairly nice generating function, and recursive formulas we can derive from that, but no closed form.

OK, the generating function and recursive formula I mentioned, because OEIS formatting doesn't make these things easy to read (Finding them? They're below the references):

To build a partition, we count how many pieces of each size there are. Pieces of size $1$? That's a factor of $(1+x+x^2+x^3+\cdots)$ in the generating function; the degree of $x^k$ tells us what those $k$ pieces of size $1$ add to. Pieces of size $2$? That's a factor of $(1+x^2+x^4+x^6+\cdots)$, with $k$ pieces giving us the $x^{2k}$ term since their sum is $2k$. Then we get $(1+x^3+x^6+x^9+\cdots)$ for pieces of size 3, and so on. Taken as a whole, the generating function for the partition numbers $p_n$ is $$f(x)=\sum_{n=0}^{\infty} p_n x^n = \prod_{j=1}^{\infty} (1+x^j+x^{2j}+x^{3j}+\cdots) = \prod_{j=1}^{\infty}\frac{1}{1-x^j}$$ For a recursive formula, we have $$p_n = \frac1n\sum_{j=0}^{n-1}\sigma(n-j)p_j$$ where $\sigma(m)$ is the sum of the divisors of $m$. I don't have a proof of that one off the top of my head, but it's certainly convenient enough to calculate with.