91Ó°ÊÓ

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

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

Let $T_k\left(n\right)$denote the number of partitions with$k$members of the set $\{1,2,…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,…,n\}$, the rest of the partition is a set of mutually exclusive sets that in union form$\{2,3,…,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,…,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,…,n\}$, by putting $1$in one of the$k$sets in the partition$\{2,3,…,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)$.