Number of involution in symmetric group

Solution 1:

Let $\tau$ be an involution. Writing $\tau$ as a product of disjoint cycles, we see that no cycle can have length greater than $3$ since $\tau$ has order $2$. It follows that $\tau$ is a product of disjoint transpositions.

Suppose that $\tau$ is a product of $k$ disjoint transpositions. Then it permutes precisely $2k$ letters so we must choose those letters out of the $n$ available. Next we must group the $2k$ letters into $k$ pairs. There are precisely $$a_k = \binom{n}{2k}\frac{(2k)!}{k!2^k} = \binom{n}{2k}(2k-1)!!$$ ways to do this so there are precisely $a_k$ involutions with $k$ disjoint transpositions.

Clearly $k$ can range from $0$ (the identity) to $\lfloor \frac{n}{2}\rfloor$ transpositions. Summing through the different values of $a_k$ gives the desired result.

Solution 2:

This seems to be explained in this wikipedia article.