# Recurrence Relations; partitions of a set

Need help trying to solve this problem.

Let $S$ be a set of $2n$ elements and let $P_n$ represent the number of Partitions of $S$ into $n$ parts, with two elements in each part.

Explain why $P_n=(2n-1)\times P_{n-1}$, for all $n\geq2$.

This is a review problem, not Homework.

HINT: Number the elements of $S$ from $1$ through $2n$. In order to form a partition of $S$ into $n$ pairs, we can begin by pairing element $1$ with one of the other $2n-1$ elements. That leaves $2n-2$ elements still to be paired.