Finding the number of elements of particular order in the symmetric group
Solution 1:
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:
Determine all possible cycle types for an element of order $k$, and then
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.
Solution 2:
Order is determined by the cycle structure. By that I mean a transposition has order $2$, a $3$-cycle has order $3$, etc. If $\sigma_1 \dots \sigma_t$ are disjoint cycles of order $r_1 \dots r_t$ then the order of $\sigma_1 \dots \sigma_t$ is $\textrm{lcm}(r_1 \dots r_t)$. So this is more of a combinatorial problem: look at each cycle structure and compute the possible permutations. Be careful of double counting. For $A_n$ you can simply restrict yourself to the even permutations.
If you're looking for an explicit way to produce elements of a given order, recall that cycle structure, thereby order, is preserved under conjugation. So you can compute all the conjugacy classes of elements of a given order (this is easy for small $n$, tedious for a large $n$).
Solution 3:
The facts below help you to find how many elements have a given order, but the combinatorial details are probably messy; I don't there is a simple formula.
Every permutation is a product of disjoint cycles, which is unique except for order.
The order of a product of disjoint cycles is the lcm of their orders.
The order of a permutation is determined by its cycle structure, which is the list of the orders of its disjoint cycles.
The number of possible cycle structures is the same as the number of the partitions of $n$.
The possible cycle structures corresponds to the conjugacy classes in $S_n$.