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!

Printable View

- March 4th 2012, 06:52 AMsexychessbabeCombinatoric problem partition a set please help
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!

- March 4th 2012, 04:58 PMundefinedRe: Combinatoric problem partition a set please help
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?".