Number of elements of order $2$ in $S_n$

Question

How many elements of order $2$ are there in $S_n$?

Using combinatorics I arrived at this:

For $n$ even ($n=2k$) there are ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} {n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{2\choose 2}\dfrac{1}{k!}$.

For $n$ odd ($n=2k+1$) there are ${n\choose 2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{3\choose 2}\dfrac{1}{k!}$

But how do I find the sums?

Seems like I have to use induction. But not quite upto there.

Thanks for the help!!

Answer 1

An element of order $2$ is a product of $k$, say, disjoint 2-cycles.

• For $k=1$, there are $\frac{n(n-1)}{2^1\cdot 1!}$ elements of order two.

• For $k=2$, there are $\frac{n(n-1)(n-2)(n-3)}{2^2\cdot 2!}$ elements of order two.

• For $k=3$, there are $\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{2^3\cdot 3!}$ elements of order two.

In the denominator of each fraction, you have a $2^k k!$, because each 2-cycle could be chosen in the form $(a, b)$ or in the form $(b, a)$ (so you need to divide by $2^k$), while the different permutations of the 2-cycles don't change the element (so you need to divide through by $k!$). Hence, you get in general:

• There are $\frac{n!}{(n-2k)!2^k\cdot k!}$ elements of order two which are the product of $k$ disjoint 2-cycles.

Then sum these to get your number! $$\text{number of elements of order two}=e_2(n)=\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{(n-2k)!2^k\cdot k!}$$ Note that the following recurrence relation holds. $$e_2(n)=e_2(n-1)+(1+e_2(n-2))(n-1)$$

Answer 2

it is probably not any help, but i think your sum may be written $f(\sqrt{2})$ where $$ f(x) = \sqrt{2}^{-n} \sum_{k=1}^{\lfloor \frac{n}2 \rfloor} \frac1{k!}\frac{d^{2k}}{dx^{2k}}x^n $$

Answer 3

If you accept a confluent hypergeometric function as a closed form, then a Computer Algebra System like Mathematica will give you
for even $n = 2w$:
$\left(-\frac{1}{2}\right)^{-w} U\left(-w,\frac{1}{2},-\frac{1}{2}\right)-1$
and for odd $n = 2w-1$:
$\left(-\frac{1}{2}\right)^{1-w} U\left(1-w,\frac{3}{2},-\frac{1}{2}\right)-1$

Answer 4

Let $n$ be a integer and $J = [\frac{n}{2}]$ and let $T_n^1 = \frac{n(n-1)}{2}$. Then the number of $j$-transpositions ($1< j\leq J$) in $S_n$ is $T_n^j=(n-1)T_{n-j} $. Therefore, the number of possible transpositions is $$\sum_{j=1}^J T_n^j = \sum_{j=1}^J (n-1)T_{n-j}.$$ For example, if $n=10$ then $\sum_{j=1}^5 T_{10}^j = 45+ 9\big(28+21+15+10 \big)$.

Answer 5

Using combinatorial classes from Flajolet and Sedgewick, Analytic Combinatorics we have for involutions the class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{CYC}_{=1}(\mathcal{Z})+ \textsc{CYC}_{=2}(\mathcal{Z})).$$

We must however account for (subtract) those permutations which consist of singletons only (the identity, a set of fixed points). This has class

$$\textsc{SET}(\textsc{CYC}_{=1}(\mathcal{Z})).$$

This gives the EGF (here we have also canceled the empty permutation -- the empty set)

$$Q(z) = - \exp(z) + \exp(z+z^2/2) = \sum_{n\ge 0} Q_n \frac{z^n}{n!}.$$

Extracting coefficients we find

$$Q_n = - n! [z^n] \exp(z) + n! [z^n] \exp(z) \exp(z^2/2) \\ = -1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} [z^{2k}] \exp(z^2/2) [z^{n-2k}] \exp(z) \\ = - 1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} [z^k] \exp(z/2) \frac{1}{(n-2k)!} = - 1 + n! \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{1}{2^k k! (n-2k)!} \\ = n! \sum_{k=1}^{\lfloor n/2 \rfloor} \frac{1}{2^k k! (n-2k)!}.$$

To get the recurrence we differentiate $Q(z)$ to obtain

$$Q'(z) = -\exp(z) + \exp(z+z^2/2) (1+z) \\ = - \exp(z) + (Q(z)+\exp(z)) (1+z) \\ = Q(z) (1+z) + z \exp(z).$$

Extracting coefficients will produce

$$n! [z^n] Q'(z) = Q_{n+1} = n! [z^n] Q(z) + n! [z^{n-1}] Q(z) + n! [z^{n-1}] \exp(z) \\ = Q_n + n! \frac{Q_{n-1}}{(n-1)!} + n = Q_n + n (Q_{n-1}+1).$$

This is OEIS A001189.