How many elements of order $2$ does Sym $6$ have?

Question

First, I will answer the following question:

''How many elements of order $2$ does Sym $5$ have?''

The answer is:

$(12),(13),(14),(15),(23),(24),(25),(34),(35),(45),(12)(34),(12)(35),(12)(45),(13)(24),(13)(25),(13)(45),(14)(23),(14)(25),(14)(35),(15)(23),(15)(24),(15)(35), $

that is, there are 22 elements of order $2$ does Sym $5$ have.

I omitted 3 products of two transpositions; the correct number for S5 is 25. Thanks @BrianM.Scott

• How many elements of order $2$ does Sym $6$ have?

I can compute as a manual but it will be too long. Is there any easy method to find it? Thanks...

Answer 1

One can always count all the elements of order $2$ in $S_6$.

Since we have six elements to play with, it's clear that elements of order two look either like $(ab)$, $(ab)(cd)$ or $(ab)(cd)(ef)$.

• First we find all the elements that look like $(ab)(cd)(ef)$. There are ${6\choose 2} = 15$ ways to create a 2-cycle $(ab)$. To get $(ab)(cd)$ we have ${4\choose 2}=6$ options left. Next, there's only one possible choice left to get $(ab)(cd)(ef)$. Finally, by canceling the $3!$ repetitions due to ordering 3 cycles, we get $$ \frac{15 \times 6 \times 1}{3!} = 15 $$

• Similarly, for $(ab)(cd)$ we have $$ \frac{15 \times 6}{2!} = 45 $$

• Finally, for $(ab)$ we have $$ {6\choose 2} = 15 $$

Therefore there are $15 + 45 + 15=75$ elements of order $2$ in $S_6$.

Answer 2

One way is to use GAP, like so:

gap> G:=SymmetricGroup(5);
Sym( [ 1 .. 5 ] )
gap> Ord2:=[];
[  ]
gap> for g in G do if Order(g)=2 then AddSet(Ord2, g); fi; od; Print(Size(Ord2));
25

and

gap> H:=SymmetricGroup(6);
Sym( [ 1 .. 6 ] )
gap> Order2:=[];
[  ]
gap> for h in H do if Order(h)=2 then AddSet(Order2, h); fi; od; Print(Size(Order2));
75

Answer 3

The sequence of these numbers is OEIS A001189; there apparently isn’t a really nice closed form, but there is a recurrence that is easy to use.

Let $a_n$ be the number of elements of order $2$ in $S_n$. Each such element $\pi\in S_n$ gives rise to a corresponding element of $S_{n+1}$ that agrees with $\pi$ on $[n]$ and fixes $n+1$. Each of the remaining elements of order $2$ in $S_{n+1}$ must be either a transposition $(k,n+1)$ for some $k\in[n]$, or the product of such a transposition a permutation of $[n]\setminus\{k\}$ of order $2$. There are $a_{n-1}$ permutations of $[n]\setminus\{k\}$ of order $2$, so

$$a_{n+1}=a_n+n(1+a_{n-1})\;,$$

where $a_1=0$ and $a_2=1$.

Answer 4

Involutions (elements of order 2) in $S_n$ are precisely the products of $c_2 \ge 1$ disjoint transpositions (2-cycles). If $c_1$ is the number of fixed points, then $$c_1 + 2c_2 = n.$$ By the cycle type counting formula, there are $$\frac{n!}{c_1! 2^{c_2} c_2!}$$ involutions of this form. Summing this over $1 \le c_2 \le n/2$ we can count the number of involutions in any $S_n$.

For $n = 5$ we have $$\frac{5!}{3! 2^1 1!} + \frac{5!}{1! 2^2 2!} = 10 + 15 = 25$$ involutions.

For $n = 6$ we have $$\frac{6!}{4! 2^1 1!} + \frac{6!}{2! 2^2 2!} + \frac{6!}{0! 2^3 3!} = 15 + 45 + 15 = 75$$ involutions.