Group Theory – Finding the Number of Elements of Particular Order in the Symmetric Group

abstract-algebrafinite-groupsgroup-theory

I know how to find the order of element in any group $G$, for example the order of $2$ in $\mathbb{Z}_5$ is $5$ as $2 + 2 + 2 + 2 + 2 = [10]_5 = 0 0$, which is the identity in $\mathbb{Z}_5$.

But, how to calculate number of element of particular order in symmetric group $S_n$?

I know how to calculate order of an element in $S_n$, for example in $S_5$, $(123)(45)$ has an order $6$. But how to calculate easily number of such elements? That is, how to calculate number of elements order $5$, number of elements of order $4$ in $S_5$? Is there is any easy formula? Also is there is any formula to calculate the number of elements of particular order in the alternating group $A_n$ as well?

Best Answer

There's not a simple formula known for this, and certain aspects of the question are the subject of ongoing research. For example, this paper summarizes some research that has been done on the maximum possible order for an element of $S_n$.

In general, the way to find the number of elements of order $k$ in $S_n$ is:

  1. Determine all possible cycle types for an element of order $k$, and then

  2. Determine the number of elements having each of these cycle types.

For step (1), you're just looking for all possible ways to partition $n$ into cycles so that the least common multiple of the cycle lengths is $k$. For example, if permutation has order six, then all the cycles must have length $1$, $2$, $3$, or $6$, with either at least one $6$-cycle or one cycle each of lengths $2$ and $3$. So if we want to count the number of permutations of order six in $S_8$, the possibilities are

  • One $6$-cycle, one $2$-cycle,
  • One $6$-cycle, two $1$-cycles,
  • Two $3$-cycles, one $2$-cycle,
  • One $3$-cycle, two $2$-cycles, and one $1$-cycle, or
  • One $3$-cycle, one $2$-cycle, and three $1$-cycles.

Step (2) is easy once you figure out step (1). In particular, the number of permutations in $S_n$ with a given cycle structure is $$ \frac{n!}{\prod_{d=1}^n (c_d)!\,d^{c_d}} $$ where $c_d$ denotes the number of cycles of length $d$. For example, the number of elements of $S_{20}$ having four $1$-cycles, five $2$-cycles, and two $3$-cycles is $$ \frac{20!}{(4!\cdot 1^4)(5!\cdot 2^5)(2!\cdot 3^2)} \;=\; 1\text{,}466\text{,}593\text{,}128\text{,}000. $$ The following table shows the number of elements of each order in $S_2$ through $S_8$. $$ \begin{array}{crrrrrrrrrrr} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 10 & 12 & 15 \\ \hline S_2 & 1 & 1 & - & - & - & - & - & - & - & - & -\\ S_3 & 1 & 3 & 2 & - & - & - & - & - & - & - & - \\ S_4 & 1 & 9 & 8 & 6 & - & - & - & - & - & - & - \\ S_5 & 1 & 25 & 20 & 30 & 24 & 20 & - & - & - & - & - \\ S_6 & 1 & 75 & 80 & 180 & 144 & 240 & - & - & - & - & - \\ S_7 & 1 & 231 & 350 & 840 & 504 & 1470 & 720 & - & 504 & 420 & - \\ S_8 & 1 & 763 & 1232 & 5460 & 1344 & 10640 & 5760 & 5040 & 4032 & 3360 & 2688 \end{array} $$ This table is entry A057731 at OEIS.

Related Question