Q.8 - A First Course in Probability

Question

Let $S$ be a given set. If, for some $k>0,S_1,S_2,\dots ,S_k$ are mutually exclusive nonempty subsets of $S$ such that 

$\underset{i=1}{\overset{k}{\cup }}{S}_i=S$, then we call the set $\left\{S_1,S_2,\dots ,S_k\right\}$ a partition of $S$. Let $T_n$ denote the number of different partitions of $\{1,2,\dots ,n\}$. Thus, $T_1=1$ (the only partition being $S_1=\left\{1\right\}$ ) and $T_2=2$ (the two partitions being $\left\{\right\{1,2,\left\}\right\},\left\{\right\{1\},\{2\left\}\right\}$, .

(a) Show, by computing all partitions, that $T_3=5,T_4=15$.

(b) Show that

$T_{n+1}=1+\sum _{k=1}^n\left(\begin{array}{l}n\\ k\end{array}\right)T_k$

and use this equation to compute $T_{10}$.

Step-by-Step Solution

Answer

a). We proved that $T3 = 5, T4 = 15$.

b). The partition in which all the items are in the same set. 

Part (a) Step 1: Given Information

Show by computing all partitions, that $T3 = 5, T4 = 15$.

Part (a) Step 2: Explanation

Calculating $T_3$ :

We can divide three items in:-

• one subset in $1$ way.
• Two subsets (a subset of one item, and a subset of two items ) in $3$ ways (the ways of choosing the single item).
• Three subsets in $1$ way.

Then $T_3=1+3+1=5$

Part (a) Step 3: Explanation

Calculating $T_4$ :

We can divide four items in:-

• One subset in $1$ way.
• Two subsets (a subset of one item, and a subset of three items) in $4$ ways (the ways of choosing the single item).
• Two subsets (two subsets of two items) in $3$ ways (half the number of the ways of choosing two items, since choosing item $1$ and $3$ is equivalent to choosing item $2$ and 4 ).
• Three subsets (two subsets of one item, and a subset of $2$ items ) in $6$ ways (the ways of choosing the two item).
• Four subsets in 1 way.

Then $T4=1+4+3+6+1=15$ Then $T_3=1+3+1=5$

Part (b) Step 1: Given Information

Show that $T_{n+1}=1+\sum _{k=1}^n \left(\begin{array}{l}n\\ k\end{array}\right)T_k$.

Part (b) Step 2: Explanation

Now let's derive this expression

$T_{n+1}=1+\sum _{k=1}^n\left(\begin{array}{l}n\\ k\end{array}\right)T_k$

We argue like that, let there be $\mathrm{n}+1$ item. We choose one item and make it special, then we have $n$ regular items and one special item. We choose $k(k=1,2,3,\dots n)$ regular items and partition them, while keeping the other $n-k$ items plus the special item in an extra subset altogether. Now for any two choices of the value of $k$. Now for every choice of the value of $k$, there are $\left(\begin{array}{l}n\\ k\end{array}\right)$ ways of choosing the regular items in the group to be partitioned, and $T_k$ ways of partitioning the $\mathrm{k}$ items, and hence the expression $\left(\begin{array}{l}n\\ k\end{array}\right)T_k$. And for every choice of the value of k, for every choice of the $k$ items, no two partitions are the same. Now every partition this way, corresponds to a partition of the $n+1$ items, but there is a partition of the $n+1$ that can't be reproduced by this way, namely the partition in which all the items are in the same set.