Lesson 5

All ways to partition \([n]\) into \(k\) non-empty subsets can naturally be divided into two classes:

• The element \(n\) forms a separate set \(\{n\}\). Then the remaining elements need to be partitioned into \(k-1\) non-empty subsets, and there are \(S(n-1,k-1)\) ways to do this.


• The element \(n\) is part of a subset with other elements. All such ways can be described as follows: first, partition \(n-1\) elements into \(k\) subsets, then add element \(n\) to one of these subsets. There are \(S(n-1,k) \cdot k\) ways to do this.