# Probability. Not for the faint of heart

• Feb 3rd 2009, 05:40 PM
zhupolongjoe
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!
• Feb 3rd 2009, 10:32 PM
Set Partition
Hello zhupolongjoe
Quote:

Originally Posted by zhupolongjoe
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
(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!

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!

• Feb 4th 2009, 04:13 AM
zhupolongjoe
I think I got it now. Thank you!
• Feb 4th 2009, 07:09 AM
zhupolongjoe
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.
• Feb 4th 2009, 08:53 AM
Plato
Quote:

Originally Posted by zhupolongjoe
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.
• Feb 4th 2009, 10:42 PM
Set Partition
Hello zhupolongjoe
Quote:

Originally Posted by zhupolongjoe
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!