<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] 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)$.
</s>