Results 1 to 7 of 7

Math Help - Probability. Not for the faint of heart

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Probability. Not for the faint of heart

    Let S be a given set. If, for some k>0, S1,S2,....Sk are mutually exclusive nonempty subsets of S such that union (i=1 to k) Si=S,
    , then we call the set {S1,S2,…,Sk} a partition of S. Let Tn denote the number of different partitions of {1,2,…,n}. Thus,T1=1(the only partition being S1={1}), and T2=2(the two partitions being {{1,2}},{{1},{2}}).
    (a)
    Show, by computing all partitions, that T3=5,T4=15.


    (b) Show that

    T(n+1)=1+summation(k=1 to n) (nchoose k)*Tk

    I honesty have no clue what this question is talking about and the lecture on the topic was pretty much her just saying 0<P(E)<1 and other easy stuff, only to get this question for homework. Please help!
    Last edited by mr fantastic; February 5th 2009 at 03:02 AM. Reason: Deleted derogatory language used to describe homework
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Set Partition

    Hello zhupolongjoe
    Quote Originally Posted by zhupolongjoe View Post
    Let S be a given set. If, for some k>0, S1,S2,....Sk are mutually exclusive nonempty subsets of S such that union (i=1 to k) Si=S,
    , then we call the set {S1,S2,,Sk} a partition of S. Let Tn denote the number of different partitions of {1,2,,n}. Thus,T1=1(the only partition being S1={1}), and T2=2(the two partitions being {{1,2}},{{1},{2}}).
    Quote Originally Posted by zhupolongjoe View Post
    (a)
    Show, by computing all partitions, that T3=5,T4=15.


    (b) Show that

    T(n+1)=1+summation(k=1 to n) (nchoose k)*Tk

    I honesty have no clue what this question is talking about and the lecture on the topic was pretty much her just saying 0<P(E)<1 and other easy stuff, only to get this crap for homework. Please help!
    You sound a bit angry about this question, but I'll do my best!

    First, let's make sure you understand what a partition is. It's essentially a way of sharing out all the elements of a set into disjoint subsets. By disjoint we mean 'having no elements in common'. So, for instance, in the second example that you are given, the set you're starting with has just two elements, the numbers 1 and 2. From this set {1, 2} you can form four possible subsets, which are:

    \oslash (the empty set), {1}, {2} and {1, 2} (the set itself)

    Now when we partition the set, we take one or more of these subsets, according to the following rules:

    • the empty set is not allowed
    • no two subsets may have any elements in common - they're disjoint, remember
    • all the elements of the original set must be included somewhere

    So there are two ways of doing this. They are:

    • {1}, {2}; and
    • {1, 2}

    So, in the notation used in the question, T_2 = 2.

    OK, so now let's look at the set {1, 2, 3} and work out what T_3 is; that's the number of ways in which we can partition this set.

    First we could have subsets with just one element each:

    • {1}, {2}, {3}

    Then we could have one subset with one element and one subset with two elements. There are three ways of doing this:

    • {1}, {2, 3}
    • {2}, {1, 3}
    • {3}, {1, 2}

    Finally, we could have all three elements in the subset which is simply the set itself:

    • {1, 2, 3}

    So there are 5 ways of partitioning this set altogether. So T_3 = 5.

    So, what have you got to do now? First, repeat the sort of thing I've just done here with the set {1, 2, 3, 4}. Do it in a logical way, similar to what I've done here, starting with subsets with just one element each, and working up to the subset containing all four elements. You should find 15 ways of partitioning this set. So T_4 = 15.

    Then, look for a way of describing how this will work in the general case with the set {1, 2, ..., n}. This should give you the answer you're looking for.

    Best of luck!

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    I think I got it now. Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Quick question: how can I use this formula?

    I have the formula (Tn+1)=1+summation(k=1 to n)(n choose k)*Tk

    I need to compute T10, the number of different partitions of {1,2,....,10}

    I don't really know what to plug in other than n=10 and I don't really know how to compute the result.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Let S be a given set. If, for some k>0, S1,S2,....Sk are mutually exclusive nonempty subsets of S such that union (i=1 to k) Si=S,
    , then we call the set {S1,S2,,Sk} a partition of S. Let Tn denote the number of different partitions of {1,2,,n}. Thus,T1=1(the only partition being S1={1}), and T2=2(the two partitions being {{1,2}},{{1},{2}}).
    (a)
    Show, by computing all partitions, that T3=5,T4=15.


    (b) Show that

    T(n+1)=1+summation(k=1 to n) (nchoose k)*Tk
    The part b is very complicated and advanced. These are known as Bell Numbers.
    If you go to the following website, you will find some good examples.
    Bell Number -- from Wolfram MathWorld
    About half way down the page you will find the formula given to you.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Set Partition

    Hello zhupolongjoe
    Quote Originally Posted by zhupolongjoe View Post
    I have the formula (Tn+1)=1+summation(k=1 to n)(n choose k)*Tk

    I need to compute T10, the number of different partitions of {1,2,....,10}

    I don't really know what to plug in other than n=10 and I don't really know how to compute the result.

    Thank you.
    The formula you have for T_{10} depends upon knowing what the values of T_1 to T_9 are, so if you want to use it, you'll have to work your way up to it. For instance, we already know T_1 through T_4, so you can find T_5 using the formula

    T_5 = 1 + \sum_{k=1}^4\begin{pmatrix}4\\k\end{pmatrix}T_k = 1 + 4T_1+6T_2+4T_3+T_4 = ...

    Note that T_0 is defined to have the value 1, so we can re-write the general formula rather more neatly as:

    T_{n+1} = \sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}T_k


    If you want to see a proof of this formula, there's one at PlanetMath: Bell number. You'll also need to understand what a 'block' is. You can find examples of that at Small Set Partitions - Wolfram Demonstrations Project.

    As I said before: best of luck!

    Grandad
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Ok. The good part is that my teacher assigned this by mistake anyways and it didn't matter lol.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: March 13th 2011, 03:39 AM
  2. Replies: 10
    Last Post: January 21st 2011, 11:47 AM
  3. Replies: 1
    Last Post: February 18th 2010, 01:54 AM
  4. Replies: 3
    Last Post: December 15th 2009, 06:30 AM
  5. Replies: 2
    Last Post: September 7th 2007, 09:56 AM

Search Tags


/mathhelpforum @mathhelpforum