# Number of permutations of order 2

Let $\sigma\in S_n$ be an element of order 2. Then $\sigma$ must be a product of $k\ge 1$ disjoint transpositions. Hence $\sigma$ can be chosen in

$\displaystyle\frac{1}{k!}\binom n2\binom{n-2}{2}\cdots\binom{n-2k+2}{2}=\frac{n!}{k!(n-2k)!2^k}$

ways. So there are exactly

$\displaystyle\boxed{\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{k!(n-2k)!2^k}}$

elements of order 2 in $S_n$.

This can also be expressed in terms of the double factorial

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!$

The following table lists several values of $n$ (left column) along with the number of elements of order 2 in $S_n$:

An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\equiv \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}\pmod 2$

Using the binomial theorem for $(1+1)^n$ and $(1-1)^n$ one deduces

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}-1\equiv 1\pmod 2$

as expected. Thus

Fact. The number of elements of order 2 in $S_n$ is odd for every $n>1$.