Number of involution in symmetric group

Question

Can any one show me on how to prove that the number of involutions in the symmetric group on $n$ letters, $$\sum_{k=0}^{\lfloor n/2 \rfloor} {n \choose 2k} (2k-1)!! = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{2^kk!(n-2k)!}$$

I've tried proving it via Young tableaux, knowing that the number of tableaux is the number of involutions, but I haven't got the right answer so far.

Answer 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.

Answer 2

Let's regard an involution as k pairs of elements of n letters where k ranges from 0(zero) to [n/2].

Firstly you pick up k elements(letters) to make the "team" L(left).
Secondly you pick up another group of k elements from the remaining (n-k) letters, and call it the "team" R(right).
Now you are ready to combine two letters, one each from both teams to make k pairs.

Let's count how many ways to do the process.

First step: nCk=n!/{k!・(n-k)!} ways.
Second step: (n-k)Pk=(n-k)!/(n-2k)! ways each.
Final step - combining letters part:the product {n!/k!・(n-k)!}・{(n-k)!/(n-2k)!} of two numbers mentioned above.

BUT we have double-counted the same set of k pairs in the third stage in many ways.

Just look at each pair and consider where each member(number) comes from.
Then you will find out that you don't know which comes from L-team/R-team.
For each set of k pairs, there are 2 ways in combining two elements from one each from both teams.
So there are 2^k ways in combining stage to make the same set of k pairs from n letters.

Now you have found out that the number of involutions in Symmetric Group of order n is the summation of the the products {n!/k!・(n-k)!}・{(n-k)!/(n-2k)!} /2^k over k where k ranges from 0(zero) to [n/2].