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}$.

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

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$

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$

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

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.