<s>[INST] 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!!
 [/INST] 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)$$
</s>