Stirling numbers of the second kind
Stirling numbers of the second kind, denoted S(n,k) or {n\brace k}, count partitions of an n-element set into k nonempty, unlabeled subsets.
Stirling recurrence: A recurrence computes Stirling numbers of the second kind from smaller values: S(n,k)=kS(n−1,k)+S(n−1,k−1). Adding one element either joins one of k existing blocks or forms a new singleton block.
Set partition: A set partition divides a set into nonempty, pairwise disjoint blocks whose union is the whole set. Each object counted by S(n,k) is a set partition with exactly k blocks.
Bell polynomial: Bell polynomials encode ways to partition labeled objects into blocks weighted by block size. Their partial forms generalize Stirling numbers by tracking weights for each block size.
Stirling triangle: The Stirling triangle arranges values S(n,k) by row n and column k. Its entries display the recurrence and the progression of partition counts.
James Stirling: James Stirling was an 18th-century Scottish mathematician known for work on infinite series and asymptotic analysis. His name is attached to the numbers, though the modern partition interpretation developed later.
Inclusion–exclusion principle: A counting method that alternately adds and subtracts overlapping cases to obtain the size of a union. It yields the explicit formula S(n,k)=1/k! times the alternating sum of jⁿ over j=0,…,k.
Binomial coefficient: A binomial coefficient counts selections of a fixed size from a finite set. It appears in the identity S(n,k)=Σⱼ₌₀ᵏ⁻¹ binom(n−1,j)S(n−1−j,k−1).
Touchard polynomial: The nth Touchard polynomial is Tₙ(x)=Σₖ S(n,k)xᵏ. Its coefficients are precisely the Stirling numbers in row n.
Boundary values of Stirling numbers: The boundary values include S(0,0)=1, S(n,0)=0 for n>0, and S(n,n)=1. They anchor the recurrence and encode the empty partition and all-singleton partition.
Nikolai D. Egorov: Nikolai D. Egorov was a Russian mathematician associated with early systematic study of set-partition numbers. His work helped establish the numbers' role in enumerating partitions.