Results 1 to 5 of 5

Math Help - Combinatorics & Partitions proof

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    55

    Combinatorics & Partitions proof

    I'm totally lost on this one... Any hints or solutions are welcome! Thanks in advance.

    For n 0, let Bn be the number of partitions of a set of size n. For example, B1 = 1, B2 = 2, B3 = 5, B4 = 15. By convention, B0 = 1. Now, let Dn be the number of partitions of a set of size n into subsets of size at least two. Show that <attachment>
    Attached Thumbnails Attached Thumbnails Combinatorics &amp; Partitions proof-proof.bmp  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Confusion over problem

    If by 'partition' you mean an unordered way to write a number n as a sum of positive integers, the first few partitions are:

    P(1) = 1, as
    1 can only be written as 1.

    P(2) = 2, as
    2 can be written as 2 or 1+1.

    P(3) = 3, as
    3 can be written as 3 or 2+1 or 1+1+1.

    P(4) = 5, as
    4 can be written as 4 or 3+1 or 2+2, 2+1+1, 1+1+1+1.

    which don't match your problem description.

    Please clarify your problem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    Well, Bi is the i:th Bell number.
    Bell number - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Partitions

    He's indeed referring to the Bell numbers, which are the number of partitions of a set (of n integers) into subsets, and not partitions of an integer.

    Dn is simply the number of partitions of a set of integers, such that no partition has less than 2 elements (also known as singleton-free partitions, or 2-restricted Bell numbers, see integer sequence A000296).

    While I can't prove the entire thing at the moment, I can say that Bi = Di + D(i+1), since if you take away all the singleton-free partitions of Bi, the remaining Bi - Di partitions will (obviously) all have at least one singleton. Group all these singletons together (partitionwise) and add the element i+1, now you have all the D(i+1) partitions.

    The proof is very likely to have something to do with the sieve principle. Also, Dn are partition analogues of derangements, if that's any help.
    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 r0r0trog View Post
    I'm totally lost on this one... Any hints or solutions are welcome! Thanks in advance.

    For n 0, let Bn be the number of partitions of a set of size n. For example, B1 = 1, B2 = 2, B3 = 5, B4 = 15. By convention, B0 = 1. Now, let Dn be the number of partitions of a set of size n into subsets of size at least two. Show that <attachment>
    Hint:

    D_n is the number of set partitions that do not include any singleton subsets.

    Let's say the original set is \{x_1, x_2, \dots , x_n\}. Say that a set partition has property i if one of the subsets in the partition is \{x_i\}. Now apply the Principle of Inclusion/Exclusion, also known as the Sieve Principle, to find the number of partitions which has none of the properties 1,2, ..., n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics - Partitions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2010, 08:09 PM
  2. Proof about Partitions of a set
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 03:09 AM
  3. Combinatorics proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 07:09 AM
  4. Replies: 0
    Last Post: December 7th 2008, 05:07 PM
  5. Combinatorics Proof
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 27th 2007, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum