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.


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.

  • $\begingroup$ Could you explain the 2nd equation to me please, I'm not entirely sure where it comes from. $\endgroup$ – Vielbein Apr 19 '16 at 1:12
  • 1
    $\begingroup$ Given that you have $j$ distinct labels and want to build a directed cycle you can distribute these into the slots on the cycle in $j!$ ways. However cycles that can be obtained from one another by a rotation (cyclic group) are the same and should count as one. The orbits under this action all have the same size and contain $j$ assignments. Therefore, divide $j!$ by $j$ to get the answer. $\endgroup$ – Marko Riedel Apr 19 '16 at 1:19
  • $\begingroup$ Makes sense, thanks! $\endgroup$ – Vielbein Apr 19 '16 at 1:31

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.