Stirling Numbers and Set Partitions

A set partition splits a collection of distinct items into non-empty, unordered groups — unordered meaning $\{A,B\}, \{C\}$ is the same partition as $\{C\}, \{B,A\}$, since it's the grouping that matters, not any labeling of the groups. The Stirling number of the second kind, written $S(n,k)$, counts the number of ways to partition $n$ distinct items into exactly $k$ non-empty groups.

These numbers satisfy a simple recurrence that mirrors how you'd build up the count by hand: to partition $n$ items into $k$ groups, either the $n$-th item joins one of the existing $k$ groups formed from the first $n-1$ items ($k$ ways to choose which group, times $S(n-1,k)$ ways to have formed them), or the $n$-th item starts a brand-new group on its own ($S(n-1,k-1)$ ways to have partitioned the rest into the remaining $k-1$ groups). This gives $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$.

As a worked example, take $n=4$ items split into $k=2$ groups. Using the recurrence with known small values $S(3,1)=1$ and $S(3,2)=3$: $S(4,2) = 2 \cdot S(3,2) + S(3,1) = 2 \cdot 3 + 1 = 7$. Checking by hand for items $\{1,2,3,4\}$ confirms exactly 7 ways to split them into two non-empty groups. Summing $S(n,k)$ over every possible $k$ from 1 to $n$ gives the Bell number, the total count of all ways to partition an $n$-item set into any number of groups.