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.
[Math] Number of ways to partition a set with $2n$ elements into unordered pairs
combinatoricsset-partition
Best Answer
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)!!$.