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!
What effort have you made? I would solve it by finding a closed-form solution with factorials, from which the recurrence easily follows, but I'm guessing there's a more direct way.
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?".