Number of involution in symmetric group 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.  

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