Stirling Numbers (Second Kind)

Stirling numbers of the second kind, written $S(n,k)$ or $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$, count the number of ways to partition a set of $n$ elements into exactly $k$ non-empty, unlabeled subsets. Intuition: Think of distributing $n$ distinguishable employees into $k$ identical project teams, where every team must have at least one member. The teams are unlabeled — only who is with whom matters, not which team is "Team A." Recurrence: $S(n,k) = k \cdot S(n-1, k) + S(n-1, k-1)$ The new element either (a) joins one of the existing $k$ groups ($k$ choices), or (b) forms a new singleton group (reducing to $k-1$ groups for the remaining $n-1$). Explicit formula (via inclusion-exclusion): $$S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n$$ Concrete example: $S(4,2) = 7$. Partition $\{a,b,c,d\}$ into 2 non-empty groups: $\{a\}|\{b,c,d\},\ \{b\}|\{a,c,d\},\ \{c\}|\{a,b,d\},\ \{d\}|\{a,b,c\},\ \{a,b\}|\{c,d\},\ \{a,c\}|\{b,d\},\ \{a,d\}|\{b,c\}$. Connection to labeled boxes: The number of surjections from $n$ elements onto $k$ labeled bins is $k! \cdot S(n,k)$. First few values: $S(1,1)=1,\ S(2,1)=1,\ S(2,2)=1,\ S(3,2)=3,\ S(3,3)=1,\ S(4,2)=7,\ S(4,3)=6$. When to use: Problems about distributing distinct objects into identical groups, counting surjections, or computing Bell numbers $B_n = \sum_{k=0}^{n} S(n,k)$. Appears in occupancy problems and in the combinatorics of moments (connecting ordinary moments to factorial moments).