Counting cycle structures in $S_n$

Is there a fast way to count all the different types of cycle structures in a Symmetric group?

More specifically: "How many elements are there in $S_8$ of cycle structure $4^2$"

Here, $4^2$ means a permutation in $S_8$ that is the product of 2 4-cycles i.e: ( 1 2 3 4 )( 5 6 7 8 ) would be an element. ( 2 4 6 8)(1 3 5 7) would also be an element. Is there a general formula that would tell me the number of elements in this set? Or do I have to just have to calculate each one? Thanks!

Solution 1:

So first of all you want to know which numbers are in which cycles. Let $s$ be the number of distinct cycle lengths (for instance, in $S_8$ with $4^2$ there is only one distinct cycle length, where as in $3^2 2$ there are two) and let $k_1,\cdots,k_s$ be the number of cycles of length $n_i$, the set $\{n_1,\cdots,n_s\}$ being the distinct cycle lengths appearing in the permutation. Let $t_i = k_{n_i} \cdot n_i$ be the number of numbers which end up in a cycle of length $n_i$ in such a permutation.

Afterwards, if the numbers $\alpha_1,\cdots,\alpha_{t_i}$ end up in cycles of length $n_i$, then there are $t_i!$ ways of ordering them in increasing order, and splitting them in groups of $n_i$ numbers, there will be $1/(k_i!n_i^{k_i})$ "double counting" (once because ordering the $n_i$-disjoint cycles in a different order gives the same permutation (because disjoint cycles commute), and again because there are $n_i$ different ways of ordering numbers in increasing order to obtain the same cyclic permutation, such as $(1234)$ or $(2341)$). So your result is $$ \binom{n}{t_1, \cdots, t_s} \prod_{i=1}^s \frac{t_i!}{k_i! n_i^{k_i}} = \frac{n!}{k_1! \cdots k_s! n_1^{k_1} \cdots n_s^{k_s}}. $$ In the case of $S_8$ and $4^2$, there are $\frac{8!}{2! \cdot 4^2}$ such permutations. Hope that helps,

Solution 2:

You can count the cycle structure in $S_n$ using combinatorial techniques. For your example, in $S_8$ you want a product of two 4-cycles: $(a_1 \, a_2 \, a_3 \, a_4)(a_5 \, a_6 \, a_7 \, a_8)$.

Start by counting the number of ways to set up the leftmost cycle. You have 8 choices for $a_1$, 7 choices for $a_2$, 6 choices for $a_3$ and 5 choices for $a_4$. But we have over counted. Notice that for any 4-cycle in $S_8$ $(a_1 \, a_2 \, a_3 \, a_4)=(a_2 \, a_3 \, a_4 \, a_1)=(a_3 \, a_4 \, a_1 \, a_2)=(a_4 \, a_1 \, a_2 \, a_3)$. This tells us that we have over counted by 4 for the first 4-cycle so we must divide by 4. This yields $\frac{8\cdot7\cdot6\cdot5}{4}$ possible 4-cycles for the leftmost cycle.

Next count the number of ways to set up the rightmost cycle. You have already used up 4 out of 8 numbers available so you only have 4 choices for $a_5$, 3 choices for $a_6$, 2 choices for $a_7$ and 1 choice for $a_8$. Again, we have over counted by four so we have $\frac{4\cdot 3\cdot 2 \cdot 1}{4}$ possible 4-cycles for the rightmost cycle.

Finally, since $(a_1 \, a_2 \, a_3 \, a_4)(a_5 \, a_6 \, a_7 \, a_8)=(a_5 \, a_6 \, a_7 \, a_8)(a_1 \, a_2 \, a_3 \, a_4)$ we need to divide by 2 (since right now we are counting say (1 2 3 4)(5 6 7 8) and (5 6 7 8)(1 2 3 4) separately).

So in $S_8$ we have $\frac{8 \cdot 7\cdot 6 \cdot 5}{4} \cdot \frac{4 \cdot 3 \cdot 2 \cdot 1}{4} \cdot \frac{1}{2}=\frac{8!}{4^2 2!}$.

(This coincides with the formula you have already been given.)

Solution 3:

The general answer is given by the following generating function. For a permutation $\sigma \in S_n$, write $c_k(\sigma)$ for the number of $k$-cycles in $\sigma$. Hence

$$\sum_{\sigma \in S_n} \prod_i z_i^{c_i(\sigma)}$$

is the generating function encoding the cycle types of all permutations in $S_n$. This polynomial divided by $n!$ is called the cycle index polynomial of $S_n$, and a beautiful generating function is known for these polynomials, namely

$$\sum_{n \ge 0} \frac{t^n}{n!} \sum_{\sigma \in S_n} \prod_i z_i^{c_i(\sigma)} = \exp \left( \sum_{k \ge 1} \frac{z_k t^k}{k} \right).$$

This is a version of the exponential formula. See this blog post for some details.

In your specific case you can set every variable except $z_4$ equal to zero, but there are substantially more elementary things you can do. The first $4$-cycle uniquely determines the second one, so think about how many ways there are to pick it (keeping in mind cyclic symmetry). Then keep in mind what happens when you switch the first and second $4$-cycles.