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?

Short answer

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

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

Step-by-step solution

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

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 localid="1649484429143" $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 $kT\_\left\{k\right\}(n-1).$

In conclusion,

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