Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is given by the number of ways of partitioning N.
For some permutation on N elements made up of $P_j$ $j$-cycles, it is trivial to see that:
$$
N = \sum_j j P_j
$$
Given some cycle structure, how can one calculate the number of elements, n, in the class pertaining to said structure?
Pierre Ramond's "Group Theory: A Physicist's Survey" gives this as:
$$
n = \frac{N!}{\prod_{j=1}^N j^{P_j} P_j!}
$$
Is this formula found by considering a binomial coefficient? I would very much appreciate it if someone could explain to me each term in this equation, specifically the denominator.
With Thanks, Sean.
Best Answer
There are at least two possible proofs, one of them by enumeration and another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle (multinomial coefficient):
$$\frac{N!}{\prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a directed cycle all orbits under the action of the cyclic group have the same size which is $j$):
$$\prod_j \frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$\prod_j \frac{1}{P_j!}.$$
This yields the answer
$$\frac{N!}{\prod_j (j!)^{P_j}} \prod_j \frac{(j!)^{P_j}}{j^{P_j}} \prod_j \frac{1}{P_j!} = \frac{N!}{\prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index of the symmetric group)
$$Z(S_N) = [z^N] \exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots\right).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} \times\cdots]$ in $N! Z(S_N)$ we get
$$N! [z^N] [\prod_j a_j^{P_j}] \prod_j \exp\left(a_j\frac{z^j}{j}\right) = N! [z^N] \prod_j \frac{z^{j P_j}}{j^{P_j} P_j!} \\ = N! [z^N] z^{\sum_j jP_j} \prod_j \frac{1}{j^{P_j} P_j!} = N! \prod_{j} \frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we have the labeled species
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}( \mathcal{A_1}\textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{A_2}\textsc{CYC}_{=2}(\mathcal{Z}) + \mathcal{A_3}\textsc{CYC}_{=3}(\mathcal{Z}) + \cdots)$$
and hence we are extracting from an EGF.