8. Let S be a given set. If, for some k> 0, S1, S2, ..., Sk are mutually exclusive nonempty subsets of S such that

$$ \bigcup_{i=1}^k S_i = S, $$

then we call the set {S1, S2...., Sk} a partition of S. Let T, denote the number of different partitions of {1, 2,..., n), and so T₁ = 1 (the only partition being S₁= [1]), and T₂ = 2 (the two partitions being {{1, 2,}}, {{1}, {2}}).

(a) Show, by computing all partitions, that T3 5, T₁ = 15.

(b). Show that

$$ T_{n+1} = 1 + \sum_{k=1}^n {n \choose k} T_k $$

and use this to compute T10-

HINT: One way of choosing a partition of n + 1 items is to call one of the items special. Then we obtain different partitions by first choosing k, k = 0, 1,..., n, and then a subset of size n k of the nonspecial items, and then any of the T partitions of the remaining k nonspecial items. By adding the special item to the subset of size n k we obtain a partition of all n + 1 items.