Stirling Numbers of the Second Kind

Stirling numbers of the second kind appear throughout discrete mathematics and its applications. In combinatorics on words and functions, $S(n,k)$ is the essential ingredient for counting surjections, via $\text{Surj}(n,k) = k!\,S(n,k)$, and summing over $k$ gives the Bell numbers $B_n = \sum_{k=0}^n S(n,k)$, the total count of set partitions — a quantity central to the study of equivalence relations on finite sets. In the Twelvefold Way framework for counting functions between finite sets under various symmetry conditions, $S(n,k)$ occupies exactly the cell corresponding to "surjections from an unlabeled domain onto an unlabeled codomain, up to relabeling the codomain," making it one of the twelve canonical counting problems. In algebra and analysis, Stirling numbers of the second kind provide the change-of-basis coefficients between the monomial basis $x^n$ and the falling factorial basis $(x)_k = x(x-1)\cdots(x-k+1)$:

a fact used in finite-difference calculus (Stirling's original motivation), in the theory of moments of discrete probability distributions, and in umbral calculus. In probability and statistics, Stirling numbers appear in the moments of the Poisson distribution and in occupancy problems (balls into unlabeled, non-empty urns). In computer science, they arise in the analysis of hashing schemes, in counting the number of ways to partition data into non-empty labeled or unlabeled clusters (relevant to clustering algorithms and combinatorial data structures), and in the enumeration of equivalence classes of finite automata states. In cryptography and coding theory, closely related surjection and partition counts arise when bounding the number of possible key-to-plaintext block assignments or analyzing collision structures in hash-based schemes. Finally, Stirling numbers of the second kind are a natural stepping stone toward Stirling Numbers of the First Kind, which perform an analogous role for counting permutations by their cycle structure rather than sets by their block structure.

Ask the tutor: How does the closed-form inclusion–exclusion formula for $S(n,k)$ get derived from the surjection count, step by step?

Think of $n$ labeled balls that must be dropped into some number of identical, unlabeled buckets, with no bucket left empty. The buckets have no names — swapping the contents of "bucket A" and "bucket B" produces the same partition, because there is no A or B to begin with. This is the essential difference from counting functions or surjections: a surjection onto $\{1,\dots,k\}$ additionally tells you which bucket is which, so it overcounts partitions by a factor of $k!$ (the number of ways to assign labels to the $k$ indistinguishable buckets). The key combinatorial move — used in the proof below and in almost every Stirling-number argument — is to isolate one distinguished element, say the largest, element $n$, and ask: does $n$ sit alone in its own block, or does it share a block with others? If $n$ is alone, the rest of the partition is an arbitrary partition of $\{1,\dots,n-1\}$ into $k-1$ blocks. If $n$ shares a block, remove $n$; what remains is a partition of $\{1,\dots,n-1\}$ into $k$ blocks, and $n$ could have been inserted into any of those $k$ blocks. This dichotomy is exactly the two terms of the recurrence.

Example 1: computing $S(6,3)$ by the recurrence, and interpreting it. We build up the needed table entries using $S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$, together with $S(n,1)=1$ and $S(n,n)=1$. Row $n=3$: $S(3,1)=1,\ S(3,2)=2^{2}-1=3,\ S(3,3)=1$. Row $n=4$:

(Check $S(4,2)=2^3-1=7$ against the closed form for $k=2$: matches.) Row $n=5$:

Row $n=6$:

We need $S(5,2) = 2^4-1 = 15$. So

Interpretation check via surjections. The number of surjections from a $6$-element set onto a $3$-element (labeled) set is $3!\, S(6,3) = 6 \cdot 90 = 540$. We can cross-check this against the inclusion–exclusion formula for surjections $[n]\twoheadrightarrow[k]$,

For $n=6,k=3$:

This matches $6 \cdot 90 = 540$ exactly, confirming $S(6,3) = 90$.

Example 2: partitioning $8$ distinguishable tasks among $4$ indistinguishable work-teams, no team idle, with an explicit further constraint. Suppose $8$ labeled tasks $\{1,\dots,8\}$ must be split into exactly $4$ nonempty, unlabeled teams — a raw count of $S(8,4)$ — but suppose additionally we want the number of such partitions in which task $1$ and task $2$ end up on different teams. We compute this via complementary counting inside $S(8,4)$, illustrating the recurrence's usefulness for auxiliary computations, not just the base numbers. First, we need $S(8,4)$. Build the table (using $S(n,1)=1$, $S(n,n)=1$, $S(n,2)=2^{n-1}-1$, and the recurrence for the rest): Row 3: $1,3,1$ Row 4: $1,7,6,1$ Row 5: $1,15,25,10,1$ Row 6: $1,31,S(6,3),S(6,4),15,1$ — we computed $S(6,3)=90$ above; now

Row 6: $1,31,90,65,15,1$. Row 7:

Row 7: $1,63,301,350,140,21,1$. Row 8:

So there are $S(8,4)=1701$ ways to split $8$ labeled tasks into $4$ nonempty unlabeled teams. Now, the number of these partitions in which tasks $1$ and $2$ lie in the same team: merge tasks $1,2$ into a single "super-task," reducing to a partition of $7$ labeled objects $\{\{1,2\},3,4,\dots,8\}$ into $4$ nonempty unlabeled blocks — exactly $S(7,4) = 350$ such partitions (this is a bijection: merging/unmerging the super-task is reversible, since the super-task's presence just says "1 and 2 are together"). Hence the number of partitions of $[8]$ into $4$ blocks with $1,2$ in different blocks is

This value $1351$ is our answer: among the $1701$ ways to form four unlabeled non-idle teams from eight labeled tasks, exactly $1351$ of them separate tasks $1$ and $2$ onto different teams.