How many cycles of each type are in $S_6$

Question

How many cycles of each type in $S_6$?

I know I can write down all cycles. I wonder if there a formula for me to quickly calculate the number of cycles of each type in $S_n$?

Answer 1

Suppose you are looking for all cycles of the form $(abc)(def)$ in $S_6$. Then do the following:

1. The number of ways to arrange six symbols without any restriction is $6!$.
2. But due to cycle structure, $(abc)=(bca)$ etc. so you have to account for all cyclical shifts that give the same permutation. For a cycle with length $3$, each cyclical shift gives the same permutation, so in all $3$ shifts give us the same permutation. So you have to compensate for that by $\frac{6!}{3}$.
3. Repeating (2) for the cycle $(def)$ as well, we get $\frac{6!}{3^2}$.
4. But disjoint cycles commute therefore $(abc)(def)=(def)(abc)$. So we have to account for all the ways in which two $3-$cycles can be permuted among themselves. So we need to compensate for this as well by $$\frac{6!}{3^2 \cdot 2!}=40.$$ This is the number of cycles of type $(abc)(def)$ in $S_6$.

Using the ideas above we can get that the number of cycles of type $(ab)(cd)(e)(f)$ in $S_6$ are $$\frac{6!}{2^2 \cdot 2! \cdot 2!}$$ Now try this chain of thought with other cycle types.

Answer 2

Here I give a general counting formula for the number of each cycle type in $S_n$ based on combinatorics.

Suppose $\mathfrak{M}=(m_1,m_2,\cdots,m_l)$ is a cycle type consisting of $l$ cycles in $S_n$ with length of $m_1,\cdots,m_l$ respectively where $m_i>1\,(1\leqslant i\leqslant l)$, $\sum_\limits{1\leqslant i\leqslant l}m_i\leqslant n$, and $r_i$ is the number of repeated $m_i$ (multiplicity of $m_i$). Then the number of $\mathfrak{M}$ is: $$ N=\binom{n}{m_1}\binom{n-m_1}{m_2}\cdots\binom{n-\sum_\limits{1\leqslant i\leqslant l-1}m_i}{m_l}\,\dfrac{(m_1-1)!\cdots(m_l-1)!}{r_1!\cdots r_l!}\tag1 $$ The combinatorial part is straightforward. Since the minimum element of each cycle is fixed, there are $(m_i-1)!$ permutation for each $m_i$ cycle selected. Since the cycles of the same length are undistinguished, their permutation must be excluded. For example, $(12)(34)$ is the same as $(34)(12)$. So the number of $(2,2)$-cycle of $S_6$ is $\binom{6}{2}\binom{4}{2}/2$.

Clearly, the number of $m$-cycle in $S_n$ from $(1)$ is $$ N_m=\binom{n}{m}(m-1)!=\dfrac{n(n-1)\cdots(n-m+1)}{m} $$ And the number of $(m_1,m_2,\cdots,m_l)$-cycle with multiplities of $(r_1,\cdots,r_l)$ in $S_n$ is $$ N=\dfrac{n!}{r_1!\,m_1^{r_1}\cdots \,r_l!\,m_l^{r_l}} $$ From $(1)$, we can easily find the number of each cycle type for $S_6$.

1. $2$-cycle $$ N=\binom{6}{2}(2-1)!=15 $$
2. $(2,2)$-cycle $$ N=\binom{6}{2}\binom{4}{2}\dfrac{(2-1)!\,(2-1)!}{2!}=45 $$
3. $(2,2,2)$-cycle $$ N=\binom{6}{2}\binom{4}{2}\binom{2}{2}\dfrac{(2-1)!\,(2-1)!\,(2-1)!}{3!}=15 $$
4. $3$-cycle $$ N=\binom{6}{3}(3-1)!=40 $$
5. $(3,2)$-cycle $$ N=\binom{6}{3}\binom{3}{2}(3-1)!\,(2-1)!=120 $$
6. $(3,3)$-cycle $$ N=\binom{6}{3}\binom{3}{3}\dfrac{(3-1)!\,(3-1)!}{2!}=40 $$
7. $4$-cycle $$ N=\binom{6}{4}(4-1)!=90 $$
8. $(4,2)$-cycle $$ N=\binom{6}{4}\binom{2}{2}(4-1)!\,(2-1)!=90 $$
9. $5$-cycle $$ N=\binom{6}{5}(5-1)!=144 $$
10. $6$-cycle $$ N=\binom{6}{6}(6-1)!=120 $$ The class equation of $S_6$ is $$ |S_6|=1+15+45+15+40+120+40+90+90+144+120=720 $$

Answer 3

Here I discuss the number of each cycle type for $S_7$ based on the formula given in the previous answer.

1. $2$-cycle $$ N=\binom{7}{2}(2-1)!=21 $$
2. $(2,2)$-cycle $$ N=\binom{7}{2}\binom{5}{2}\dfrac{(2-1)!\,(2-1)!}{2!}=105 $$
3. $(2,2,2)$-cycle $$ N=\binom{7}{2}\binom{5}{2}\binom{3}{2}\dfrac{(2-1)!\,(2-1)!\,(2-1)!}{3!}=105 $$
4. $3$-cycle $$ N=\binom{7}{3}(3-1)!=70 $$
5. $(3,2)$-cycle $$ N=\binom{7}{3}\binom{4}{2}(3-1)!\,(2-1)!=420 $$
6. $(3,2,2)$-cycle $$ N=\binom{7}{3}\binom{4}{2}\binom{2}{2}\dfrac{(3-1)!\,(2-1)!\,(2-1)!}{2!}=210 $$
7. $(3,3)$-cycle $$ N=\binom{7}{3}\binom{4}{3}\dfrac{(3-1)!\,(3-1)!}{2!}=280 $$
8. $4$-cycle $$ N=\binom{7}{4}(4-1)!=210 $$
9. $(4,2)$-cycle $$ N=\binom{7}{4}\binom{3}{2}(4-1)!\,(2-1)!=630 $$
10. $(4,3)$-cycle $$ N=\binom{7}{4}\binom{3}{3}(4-1)!\,(3-1)!=420 $$
11. $5$-cycle $$ N=\binom{7}{5}(5-1)!=504 $$
12. $(5,2)$-cycle $$ N=\binom{7}{5}\binom{2}{2}(5-1)!\,(2-1)!=504 $$
13. $6$-cycle $$ N=\binom{7}{6}(6-1)!=840 $$
14. $7$-cycle $$ N=\binom{7}{7}(7-1)!=720 $$ The class equation of $S_7$ is $$ |S_6|=1+21+105+105+70+420+210+280+210+630+420+504+504+840+720=5040 $$