Stirling numbers of the second kind

Stirling numbers of the second kind answer a fundamental counting question in discrete mathematics: given n distinct objects, in how many ways can you partition them into exactly k non-empty unlabeled groups? The answer is written S(n,k) or sometimes {n choose k} with curly braces. These numbers appear whenever you group people into teams without naming the teams, split a set of keys into unlabeled buckets, count surjective functions up to a factorial factor, build Bell numbers as a sum over k, or grade homework that asks for set partitions rather than permutations. This capability accepts non-negative integers n (the number of items) and k (the number of non-empty subsets) and returns the exact S(n,k) as a decimal string computed with BigInt dynamic programming, so values far beyond ordinary safe-integer limits stay correct digit for digit. Inputs with a negative k or with k greater than n are rejected with a clear validation error instead of a silent zero or a wrong answer.

How Stirling numbers of the second kind are defined

A Stirling number of the second kind S(n,k) counts the partitions of an n-element set into exactly k non-empty unlabeled subsets. Order inside a subset does not matter, and the subsets themselves are not ordered: the partition {{1,2},{3}} is the same as {{3},{1,2}}. The standard recurrence is S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitively, when you add the newest element n, either it forms a singleton of its own (then the remaining n−1 elements form k−1 subsets, counted by S(n−1,k−1)), or it joins one of the k existing subsets in a partition of the first n−1 elements into k blocks (k choices, times S(n−1,k)). Base cases that close the table are S(0,0) = 1, S(n,0) = 0 for n > 0, S(0,k) = 0 for k > 0, S(n,1) = 1, and S(n,n) = 1.

Classic textbook checks include S(3,2) = 3, S(4,2) = 7, S(5,2) = 15, and S(5,3) = 25. The Bell number B_n, the total number of partitions of an n-set with any number of blocks, is the sum of S(n,k) over k from zero to n. Related but different objects include Stirling numbers of the first kind (which track permutations by cycle count) and binomial coefficients (which choose elements without partitioning the rest).

This implementation never uses floating-point approximation, Monte Carlo sampling, or external tables: it fills a dynamic-programming row with exact BigInt arithmetic so every digit is correct. The path is fully deterministic—no random seeds, no clocks, no network, and no model drift—so the same n and k always yield the same string.

Where second-kind Stirling counts show up in real work

Combinatorics courses and programming contests constantly ask how many ways to split n labeled people into k unlabeled teams, how many equivalence relations on n elements have exactly k classes, or how many ways to distribute n distinct gifts into k identical non-empty boxes—all of which equal S(n,k). Algorithm designers use Stirling second-kind tables when analyzing set-partition data structures, clustering sketches with a fixed number of clusters, or counting the ways a recursive process can group intermediate results.

Probability and statistics courses connect S(n,k) to the number of ways to assign n distinct outcomes into k non-empty unlabeled bins and to the closed form for the number of surjections from an n-set onto a k-set, which is k! · S(n,k). Educators and interview prep often show a short triangle of small S(n,k) values; computing a single entry in one call keeps interactive demos aligned with textbooks and answer keys without hand-maintaining large tables.

If you later need Stirling numbers of the first kind, Bell numbers alone, surjection counts with the k! factor already applied, or an explicit listing of partitions rather than the count, treat those as separate search intents rather than overloading this landing.