Stirling Numbers

Why Stirling numbers matter

Stirling numbers are the bridge between three otherwise-separate counting problems: set partitions, cyclic permutations, and the falling-factorial / monomial change of basis. Knowing the bridge is what lets you convert between formulations and exploit each one's natural symmetries.

• Enumerative combinatorics. Stirling numbers count distributions of distinguishable objects into indistinguishable boxes (S), or into ordered boxes (k! · S), or into trees with prescribed cycle structure (c). The "twelvefold way" of distribution problems uses S, c, multinomials, and binomials as the four basic counts.
• Generating functions. The exponential generating function Σ S(n, k) x^n/n! = (e^x − 1)^k / k! is the cornerstone of analytic combinatorics for set partitions; Σ B(n) x^n/n! = exp(e^x − 1) similarly for total partitions. Once you have the EGF you can extract asymptotics (saddle-point method) or convolve with other species.
• Statistical mechanics and physics. Bell numbers count the number of equivalence classes of subsystems; Stirling numbers appear in the normal-ordering of bosonic creation/annihilation operators (Bell-Touchard polynomials are the operator analogue). Random partitions in physics (Ewens distribution, Chinese restaurant process) use first-kind Stirling weights.
• OEIS staples. Both Stirling kinds are central sequences in the Online Encyclopedia of Integer Sequences (A008275, A008277, A000110 for Bell). They appear as auxiliaries in hundreds of other sequences and identities.
• Symmetric functions. The change-of-basis matrices between elementary, complete homogeneous, monomial, and power-sum symmetric functions involve Stirling-like quantities (Lah numbers, Whitney numbers) — Stirling numbers are the simplest case in this larger family.
• Random permutations. The number of permutations of n elements with k cycles is c(n, k); dividing by n! gives the probability that a uniformly random permutation has exactly k cycles. Expected number of cycles is the harmonic number H_n ≈ log n + γ; the Erdős-Turán law tells you the cycle-count distribution is asymptotically normal with mean and variance both ~ log n.
• Computer science. Hashing analysis (probability of k bins occupied), random graph component counts, and the analysis of random sorting algorithms all invoke Stirling numbers of the second kind through balls-in-bins arguments.

Closed forms and small tables

Closed-form expression for the second kind via inclusion-exclusion:

S(n, k) = (1/k!) Σ_{j=0}^{k} (−1)^j C(k, j) (k − j)^n.

Equivalently, k! · S(n, k) counts the surjections from {1, …, n} to {1, …, k}. The first few values:

• S(0, 0) = 1; S(n, 0) = 0 for n > 0; S(n, 1) = 1; S(n, n) = 1; S(n, n − 1) = C(n, 2).
• S(2, 2) = 1; S(3, 2) = 3; S(4, 2) = 7; S(5, 2) = 15; S(6, 2) = 31 — note 2^(n−1) − 1.
• S(4, 3) = 6; S(5, 3) = 25; S(6, 3) = 90; S(7, 3) = 301.
• S(5, 2) = 15: partitions of {1,2,3,4,5} into two blocks — pick a subset (excluding empty and full set) and divide by 2. (2^5 − 2)/2 = 15.
• Bell numbers: B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, B(5) = 52, B(6) = 203, B(7) = 877.

For the first kind:

• c(n, n) = 1 (the identity permutation has n fixed-point cycles); c(n, 1) = (n − 1)! (the n-cycles).
• c(n, n − 1) = C(n, 2) — exactly one 2-cycle and (n − 2) fixed points; choose which 2 elements form the transposition.
• Sum: Σ_k c(n, k) = n! — every permutation has some cycle decomposition.

Generating functions and identities

The two-variable EGFs encode the recursions cleanly.

• Second kind, EGF in n. Σ_{n ≥ k} S(n, k) x^n / n! = (e^x − 1)^k / k!. The "exp combinatorial construction" reads: a set partition is a set of non-empty blocks, blocks have EGF e^x − 1, applying SET = exp gives exp(e^x − 1), and selecting k blocks gives the (e^x − 1)^k / k! row.
• First kind, EGF. Σ_{n ≥ k} c(n, k) x^n / n! = (−log(1 − x))^k / k!. A permutation is a set of cycles, cycles have EGF −log(1 − x), apply SET = exp.
• Bell EGF. Σ B(n) x^n / n! = exp(e^x − 1). Touchard's polynomial T_n(x) = Σ_k S(n, k) x^k satisfies T_n(1) = B(n) and T_n(−1) = (−1)^n B_n^{−} (complementary Bell number).
• Dobinski's formula. B(n) = (1/e) Σ_{k=0}^{∞} k^n / k! — a beautiful series for Bell numbers that connects them to Poisson moments.
• Vandermonde-Chu identity. Stirling numbers transform multinomial-style identities between falling factorials and powers; the simplest is x^n = Σ_k S(n, k) (x)_k where (x)_k = x(x − 1) ⋯ (x − k + 1).

Cycle structure of random permutations

The probability that a uniformly random permutation of n elements has exactly k cycles is c(n, k) / n!. Expected cycle count is H_n = 1 + 1/2 + ⋯ + 1/n ≈ log n + γ. Variance is also approximately H_n − π^2/6. Goncharov's theorem and Arratia-Tavaré show the cycle counts (number of 1-cycles, number of 2-cycles, …) converge to independent Poisson variables — the Ewens-Sampling-Formula limit. This underlies all of population-genetics neutral-allele theory.

Stirling numbers vs. Stirling's approximation

Confusion is constant between Stirling numbers (these counting quantities) and Stirling's approximation n! ~ √(2πn) (n/e)^n. Both are due to James Stirling — the same Scottish mathematician — but they are unrelated topics. Stirling numbers are exact integer counts. Stirling's approximation is an asymptotic estimate. The latter shows up in factorial calculations everywhere; the former parametrizes set-partition and cycle-count enumeration.

Common misconceptions

• "Stirling = approximation of n!" Stirling numbers are a different topic by the same author. Stirling's approximation gives the asymptotic size of n!; Stirling numbers count partitions and cycles.
• "First and second kind are interchangeable." They count different things. S(n, k) counts unordered set partitions; c(n, k) counts cyclic permutations. The matrices they form are mutual inverses, but the combinatorial meanings differ.
• "Both are positive." Signed first-kind s(n, k) = (−1)^{n−k} c(n, k) carries a sign so that the change-of-basis matrices invert exactly. Forgetting the sign breaks the falling-factorial identities.
• "S(n, k) is symmetric in n and k." No symmetry — S(n, k) = 0 for k > n; S(n, k) reaches a maximum near k ~ n/log n; the row sum (Bell number) blows up.
• "Computing S(n, k) is hard." The recursion is two array lookups; an n × k table fills in O(n k) time. Closed-form via inclusion-exclusion is also tractable for moderate k.
• "Stirling numbers and binomials are similar." Pascal's triangle obeys C(n, k) = C(n − 1, k) + C(n − 1, k − 1); Stirling second kind has the k coefficient — S(n, k) = k · S(n − 1, k) + S(n − 1, k − 1) — that breaks the binomial-style symmetry.