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

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!!

• I do not think there is a closed form for this sum. – Chris Godsil Aug 11 '14 at 13:39
• See this for some references etc oeis.org/A001189 – Mark Bennet Aug 11 '14 at 14:02

## 3 Answers

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 \choose 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 \choose 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)$$

• My question is how do i find the sum of what i asked?? – tattwamasi amrutam Aug 11 '14 at 13:49
• This is exactly what I wrote – tattwamasi amrutam Aug 11 '14 at 14:10
• @tattwamasi Well, it isn't exactly what you wrote. As the comments to your post point out, it is unlikely that there is a closed-form of this sum (this is especially implied by the oeis link, where no closed-form is given). So I thought it would be helpful, at lease to others, to write down the sum as neatly as possible. So I gave you (what I considered to be) a neater way of writing the terms of the sum, as well as a recurrence relation. – user1729 Aug 11 '14 at 14:26

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$$

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$