Q. 2.16 - A First Course in Probability

Question

Let $T_k\left(n\right)$denote the number of partitions of the set$1,...,n$ into$k$ nonempty subsets, where$1\le k\le n$. (See Theoretical Exercise $8$ for the definition of a partition.) Argue that

$T_k\left(n\right) = k{T}_k(n - 1) + T_k-1(n - 1)$

Hint: In how many partitions is$1$ a subset, and in how many$1$ elements of a subset that contains other elements?

Step-by-Step Solution

Answer

Note that $T_k\left(n\right)$is the number of partitions with$k$ members of any set with $n$members.

Count separately the partitions with$\left\{1\right\}$ as a member and without.

Step 1 Given Information.

$T_k\left(n\right)$ denote the number of partitions of the set

$\left\{1,...,n\right\}$ into$k$ nonempty subsets, where$1\le k \le n.$

Step 2 Explanation.

Let $T_k\left(n\right)$denote the number of partitions with$k$ members of the set $\{1,2,\dots n\}$ (or any other set with$n$ elements).

To express$T_k\left(n\right)$ using a recursion note:

Some of the partitions have$1$ a separate subset, and some don't.$T_k\left(n\right)$ is the sum of the number of partitions where $\left\{1\right\}$is an element and the number of partitions where $1$is in a subset with more than one element.

    It $\left\{1\right\}$is an element of the partition with$k$ members$\{1,2,\dots ,n\}$, the rest of the partition is a set of mutually exclusive sets that in union form$\{2,3,\dots ,n\}$ - a partition in$k-1$sets of a set with $n-1$elements. The number of those partitions possible is$T_{k-1}(n-1)$.

It $1$is an element of one of the $k$sets in the partition of a set with$n$ elements. Disregarding $1$the observed partition is a partition in$k$ sets of $\{2,3,\dots ,n\}$ - a set of$n-1$ elements. So there are $T_k(n-1)$such partitions, each of them can induce different$k$ partitions into$k$ sets of a set$\{1,2,\dots ,n\}$, by putting $1$in one of the$k$ sets in the partition$\{2,3,\dots ,n\}$. The number of these partitions is $k T\_\left\{k\right\}(n-1).$

In conclusion,

$T_k\left(n\right)=k{T}_k(n-1)+T_{k-1}(n-1)$.