Orders of a symmetric group

Solution 1:

The possible elements of $S_5$ are given by the various partitions of $5$. For example, $(i_1i_2)(i_3i_4i_5)$ is an element of $S_5$ corresponding to the partition $5=2+3$.

To count the number of such elements, we have $5$ choices for $i_1$ after which we have $4$ choices for $i_2$. We must then divide by $2$ because $(i_1i_2) = (i_2i_1)$. Hence we have $(5)(4)/2 = 10$ possibilities for $(i_1i_2)$. Once we have chosen $i_1$ and $i_2$, we then have $3$ choices for $i_3$, 2 choices for $i_4$ and one remaining choice for $i_5$ giving $6$ possibilities for $(i_3i_4i_5)$. However we observe that, for example, $(345) = (534) = (453)$ (i.e. each three cycle yields two other equivalent 3-cycles). Thus we have $6/3 = 2$ possibilities for $(i_3i_4i_5)$.

This gives $$\frac{(5)(4)}{2}\cdot 2 = 20$$ possibilities for elements of the form $(i_1i_2)(i_3i_4i_5)$.

Can you generalize this for other elements of the group?

Solution 2:

John's got you on the first part. I'll answer your second question.

Facts:

1. Every element of $S_n$ can be written as the product of disjoint cycles.

2. The order of the product of disjoint cycles is the least common multiple of the orders of those cycles. In other words, if $\pi=\pi_1\cdots\pi_n$, $o(\pi)=\mbox{lcm}\{o(\pi_1),\ldots,o(\pi_n)\}$.

So what's the maximum order of an element of $S_5$?

When making a cycle in $S_5$, you only have $5$ numbers to work with (in cycle notation). How many ways can you make disjoint cycles using only $5$ numbers? What's the biggest $\text{lcm}$ you can find this way?

Now how about $S_n$?

There's no easy closed form for this, but I'm sure you've guessed this 'formula': it's the maximum $\text{lcm}$ attainable from the integer partitions of $n$. This is called Landau's function.

Solution 3:

Since it's been proposed that a similar question be closed as a duplicate of this one, I'll derive the number of permutations corresponding to a given cycle type in more generality.

Consider a cycle structure with $j_k$ cycles of length $k$, with $\sum_kkj_k=n$, and imagine it written out as pairs of parentheses enclosing appropriate numbers of slots. Each of the $n!$ assignments of the numbers from $1$ to $n$ to the slots yields a permutation, and we want to know how many are distinct.

Within each cycle of length $k$, there are $k$ cyclic permutations of the entries that would yield the same cycle. Among $j_k$ cycles of length $k$, there are $j_k!$ permutations that merely rearrange cycles of the same length. Thus $\prod_kk^{j_k}j_k!$ assignments lead to the same permutation, so the number of distinct permutations is

$$\frac{n!}{\prod_kk^{j_k}j_k!}\;.$$

See also this Wikipedia section.