Results 1 to 2 of 2

Math Help - Combinatoric problem partition a set please help

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    home
    Posts
    2

    Combinatoric 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Re: Combinatoric problem partition a set please help

    Quote Originally Posted by sexychessbabe View Post
    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?".
    Last edited by undefined; March 4th 2012 at 06:18 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Even vs. Odd in a combinatoric proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 2nd 2011, 02:48 AM
  2. Two combinatoric problems
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 21st 2010, 06:16 PM
  3. partition problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2008, 10:54 PM
  4. combinatoric thing
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 11th 2008, 01:48 AM
  5. combinatoric identity
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 17th 2007, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum