Let S be a set of 2n elements and let pn be the number of partitions of S into n parts, with two elements in each part. Then p1=1 and p2=3. Explain why pn = (2n-1)pn-1 for n>=2. Thanks!
Edit: Oh okay, I see it now. It's actually very easy once you see it. Hint: List elements on paper for some small n, then think about the question, "Which element gets matched with the first element?".