Lesson 4

A Stirling number of the second kind \(S(n,k)\) is defined as the number of ways to partition \([n]\) into \(k\) non-empty subsets (pronounced as “\(k\) subsets of \(n\)”). For example, \(S(4,2)=7\):

1. \(\{1,2,3\} \cup \{4\}\),
2. \(\{1,2,4\} \cup \{3\}\),
3. \(\{1,3,4\} \cup \{2\}\),
4. \(\{2, 3, 4\} \cup \{1\}\),
5. \(\{1,2\} \cup \{3,4\}\),
6. \(\{1,3\} \cup \{2,4\}\),
7. \(\{1,4\} \cup \{2,3\}\).

Problem. Compute \(S(10, 5)\).