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!!
 A: 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)$$
A: 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
$$
A: 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$
A: 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)$.
A: 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.
