91Ó°ÊÓ

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+\underset{k=1}{\overset{n}{∑}} \left(\begin{array}{l}n\\ k\end{array}\right)T_k$.

Now let's derive this expression

$T_{n+1}=1+\underset{k=1}{\overset{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,…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.