What are the elements of order $n$ in symmetric group $S_n$?

Question

Title explains it nicely :-) I'm interested in listing/generating them all for small n, up to n=12 or so.

Answer 1

The order of an element of $S_n$ is the least common multiple of the size of its cycles.

So if $n$ is a prime power, then the only way this is possible is if one cycle is of length $n$. And there are $(n-1)!$ cycles of length $n$ in $S_n$.

So you are left with $n=6$, $n=10$, and $n=12$.

For general $n$, the lengths of the cycles (of an element of order $n$) must add up to $n$ and be divisors of $n$. If the lengths of the cycles are $\ell_1,\dots,\ell_k$ then $\mathrm{lcm}(\ell_1,\dots,\ell_k)=n$ and $\ell_1+\dots+\ell_k=n$.

For $n=6$, the only way for this to happen is if $k=3,\ell_1=3,\ell_2=2,\ell_3=1$ or $k=1$ and $\ell_1=6$.

We can enumerate the latter case as for prime power. Then you have to list the cases where there is one cycle of order $3$, one cycle of order $2$, and one cycle of order $1$. There are $6\times \frac{6!}{2\cdot 3}$ of this form, I think.

Unfortunately, for $n=10$, you have to enumerate $k=5, \ell_1=5,\ell_2=2,\ell_3=\ell_4=\ell_5=1$ and $k=4,\ell_1=5,\ell_2=\ell_3=2,\ell_4=1$.

So, as a general rule, this problem gets much harder as $n$ gets bigger.