Results 1 to 6 of 6

Math Help - Ways to partition [n] (the power set of n)

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Ways to partition [n] (the power set of n)

    How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

    There are \sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right) partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

    There are \left({n\atop n-2}\right) partitions of [n] into n-1 blocks.

    Did I get this one correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by oldguynewstudent View Post
    How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

    There are \sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right) partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

    There are \left({n\atop n-2}\right) partitions of [n] into n-1 blocks.

    Did I get this one correct?
    Stirling numbers of the second kind - Wikipedia, the free encyclopedia

    (I've actually done research on this topic!)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

    There are \sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right) partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

    There are \left({n\atop n-2}\right) partitions of [n] into n-1 blocks.

    Did I get this one correct?
    What do you mean by "power set of n"? An example of a power set is:

    A=\{1,a\}

    \mathcal{P}(A)=\{\emptyset,\{1\},\{a\},\{1,a\}\}

    I've noticed in the past you used [n] to mean \{1,2,\dots,n\}. So, what are we talking about here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by undefined View Post
    What do you mean by "power set of n"? An example of a power set is:

    A=\{1,a\}

    \mathcal{P}(A)=\{\emptyset,\{1\},\{a\},\{1,a\}\}

    I've noticed in the past you used [n] to mean \{1,2,\dots,n\}. So, what are we talking about here?
    OOOPS, I was tired. Yes I meant the second. \{1,2,\dots,n\}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

    There are \sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right) partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

    There are \left({n\atop n-2}\right) partitions of [n] into n-1 blocks.

    Did I get this one correct?
    I don't think you have the first one quite right. Consider what happens when n is even. How many partitions of [n] are there into sets of size n/2?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by awkward View Post
    I don't think you have the first one quite right. Consider what happens when n is even. How many partitions of [n] are there into sets of size n/2?
    Yes, I saw the post about Stirling numbers of the second kind. The formula worked for 5 but not for 6. Funny that the problem was 3 sections ahead of Stirling numbers of the second kind!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. partition help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 28th 2010, 03:35 AM
  2. Replies: 1
    Last Post: June 18th 2010, 06:51 PM
  3. partition of unity
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 13th 2009, 08:28 AM
  4. Partition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2008, 02:39 AM
  5. Partition help!!!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 15th 2008, 08:57 PM

Search Tags


/mathhelpforum @mathhelpforum