Number of ways to partition a set with $2n$ elements into unordered pairs In how many ways can I partition $S = \{1,2,\cdots,2n\}$ into $n$ disjoint $2$ element subsets. Suppose if I subsets of $S$ were $S_{1},S_{2},\cdots,S_{n}$, then I can choose $S_{1}$ in $\binom{2n}{2}$ ways after choosing $S_{1}$ I can choose $S_{2}$ in $\binom{2n-2}{2}$ ways and so on. So the total number of ways is $$\binom{2n}{2}\cdot \binom{2n-2}{2} \cdot \binom{2n-4}{2} \cdots \binom{2n}{2}$$ I feel somehow this is not right as I  have over counted.
 A: Let $a_n$ be the number of ways to partition $\{1,\dots, 2n\}$. Then $a_{n+1}=a_{n}+(2n)(2n-1)a_{n-1}$, because either $2n+2$ and $2n+1$ are in the same set, and we have $a_n$ ways to finish, or they are in different sets and then there are $(2n+2)(2n+1)a_{n-1}$ ways to finish.
Now by induction it is easy to see that the answer is $(2n-1)!!=(2n-1)(2n-3)\dots 3\cdot 1$.
You could have also found this by dividing $\binom{2n}{2}\cdot \binom{2n-2}{2} \cdot \binom{2n-4}{2} \cdots \binom{2n}{2}$ by $n!$, because you counted every partition exactly $n!$ times. This gives the same answer because $\frac{(2n)!}{2^nn!}=(2n-1)!!$.
A: Consider any arrangement of the numbers $1,2,\ldots,2n$ in a row. There are $(2n)!$ such arrangements. Each such arrangement gives raise to $n$ disjoint sets of 2 elements (simply pick the first two for the first subset, next two for the next etc). The set of $n$ disjoint subsets is counted $n!2^n$ times since we get the same disjoint sets when we permute the $n$ pairs among themselves in $n!$ ways and also permute elements in each pair in 2 ways and hence $2^n$ ways in the $n$ pairs. Thus the required number is $\frac{(2n)!}{2^n n!}$. 
A: To avoid overcounting you can first choose which of the $2n-1$ elements to be matched with the element $2n$. This can be done in $2n-1$ ways. Then you can choose which of the remaining $2n-3$ elements to be matched with the next largest unmatched element. Continuing this process yields all possible matchings, which are $(2n-1)(2n-3)...1 = (2n-1)!!$
