How many elements π in $S_n$ such that $π^2 = e$ (the order of π is 1 or 2)?

Question

For example in $S_3$, there are 4, namely: e , (01)(2), (02)(1), and (12)(0).

In $S_4$ , i think there are 1 + 6 + 6 = 13.

The identity e: gives 1, Permutation in the form of (ab)(c)(d) : 6, In the form of (ab)(cd) : 6

But i had a feeling it must be 14 or something even... (Because 4! - 13 = 11 which is cannot be partitioned in pairs) What am i missing ?

Also, Is there a way to dertermine how many such element in $S_n$ ?

Tnk u in advance

Answer 1

You can show that you can write every element of $S_n$ as a product of disjoint cycles. This gives you an easy way to determine the order of an element. Let $\pi\in S_n$, then

$$\pi=(c_{11}...c_{1t_1})(c_{21}...c_{2t_2})...(c_{m1}...c_{mt_m}).$$

Then to compute the order of $\pi$ we look at the least common multiple of $t_1,...,t_m$. In order for the order of $\pi$ to be $1$ or $2$ we require that $t_1,...,t_m\leq 2$. So we see that if we ignore $1-$cycles an element has order $1$ or $2$ if and only if it is the product of disjoint $2-$cycles (transpositions) or it is $e$ (technically $e$ is the product of no $2-$cycles). This allows us to calculate the number of elements of order $1$ or $2$. We simply count how many ways we can have a product of disjoint transpositions.

For $n=4$ there are $\binom{4}{2}\binom{2}{2}\frac{1}{2}=3$ ways to find a product of $2$ $2-$cycles. There are $\binom{4}{2}=6$ ways to find a product of $1$ $2-$cycle. Lastly there is $1$ way to find a product of no $2$-cycles. This gives us $10$ elements of order $1$ or $2$

Answer 2

You seem to be double-counting the elements of $S_4$ with cycle type $(2, 2)$: There are only three, namely, $(12)(34)$, $(13)(24)$, $(14)(23)$.

---

More generally, a permutation $\sigma \in S_n$ satisfies $\sigma^2 = e$, i.e., is an involution, if its cycle type contains only $1$'s and $2$'s, that is, if it is a product of (possibly zero) disjoint transpositions.

The number of permutations with $k$ transpositions and $n - 2 k$ fixed points is, in multinomial notation, $$\frac{1}{k! (n - 2 k)!}{{n}\choose{1, \ldots, 1, 2, \ldots, 2}} = \frac{n!}{2^k k! (n - 2 k)!} :$$ The multifactorial counts the number of ways to put $n$ labeled elements in $n - k$ bins so that $n - 2 k$ bins have $1$ element and $k$ bins have $2$ elements. The labeling on the bins of a given size are irrelevant, so we divide the multinomial by $k! (n - 2 k)!$ as indicated.

For example, for the given case $n = 4$, we can have

• $k = 0$ transpositions (there are $\frac{1}{0! 4!} {4 \choose{1, 1, 1, 1}} = 1$ of these, namely the identity),
• $k = 1$ transpositions (there are $\frac{1}{1! 2!} {4 \choose{1, 1, 2}} = 6$ of these, the transpositions themselves), or
• $k = 2$ transpositions (there are $\frac{1}{2! 0!} {4 \choose{2, 2}} = 3$ of these, the double transpositions).

Summing over the possible values of $k$ gives a general formula number $T_n$ of involutions in $S_n$: $$T_n = \sum_{k = 0}^{\lfloor\frac{n}{2}\rfloor} \frac{n!}{2^k k! (n - 2 k)!} .$$ The first few values are $T_1 = 1$, $T_2 = 2$, $T_3 = 4$, $T_4 = 10$, $T_5 = 26$.

This turns out to be a well-known sequence, A000085, Number of self-inverse permutations on $n$ letters, also known as involutions; number of standard Young tableaux with $n$ cells. See that link for other interpretations and various formulas for and identities of this sequence.

For more references, see the second paragraph of the introduction of this 1957 article by Miksa, Moser, and Wyman.