Stirling Numbers and Partition Functions

Stirling numbers count the ways to partition or arrange sets, bridging factorials, powers, and combinatorics. The Stirling numbers of the first kind

c (n, k)

count permutations by cycles; the second kind

S (n, k)

count set partitions into blocks. Together with the Bell numbers

B_{n}

and partition function

p (n)

, they form the backbone of enumerative combinatorics. Studied by James Stirling (1730), with deep ties to Euler, Bell, and Hardy–Ramanujan.

Stirling numbers are two families of integers that mediate between the ordinary power basis $x^{n}$ and the falling-factorial basis $x^{\underline{k}} = x (x - 1) \dots (x - k + 1)$ . The second-kind numbers $S (n, k)$ count the partitions of an $n$ -element set into exactly $k$ nonempty unlabeled blocks; the first-kind numbers count permutations of $n$ elements with exactly $k$ cycles. Their row sums give the Bell numbers (total set partitions), while the integer-partition function $p (n)$ counts unordered ways to write $n$ as a sum of positive integers — a superficially similar but profoundly different problem. The surprising fact: although $p (n)$ has no simple closed form, its asymptotics $p (n) \sim \frac{1}{4 n 3} e^{π 2 n /3}$ were pinned down exactly by Hardy and Ramanujan using analysis, not counting.

The Core Insight

A power $x^{n}$ counts functions; a falling factorial $x^{\underline{k}}$ counts injections. Stirling numbers are precisely the change-of-basis coefficients between these two natural polynomial bases. The combinatorial meaning (cycles, blocks) emerges automatically because the algebra of the bases encodes the act of "choosing and grouping." All of Stirling theory is the dictionary between this algebraic fact and its counting shadow.

Formal Statement

Stirling Numbers of the Second Kind

S (n, k)

(also written

{k n}

) is the number of ways to partition a set of

n

distinguishable objects into exactly

k

nonempty, unlabeled, disjoint blocks. By convention

S (0, 0) = 1

S (n, 0) = 0

for

n > 0

, and

S (n, k) = 0

for

k > n

x^{n} = k = 0 \sum n S (n, k) x^{\underline{k}}, x^{\underline{k}} = x (x - 1) \dots (x - k + 1)

⟳Count functions from

[n]

[x]

two ways — total functions give

x^{n}

; classify by the image of size

k

, choose the image (

(k x) k!

x^{\underline{k}}

) and partition the domain (

S (n, k)

S (n, k) = \frac{1}{k !} j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

⟳Inclusion–exclusion on surjections from

[n]

onto

[k]

; the number of surjections is

k! S (n, k)

, and we subtract maps missing

j

chosen target elements.

Stirling Numbers of the First Kind

The unsigned Stirling numbers of the first kind $c (n, k) = [k n]$ count the permutations of $n$ elements having exactly $k$ disjoint cycles. The signed version $s (n, k) = (- 1)^{n - k} c (n, k)$ provides the inverse change of basis.

x^{\overline{n}} = k = 0 \sum n c (n, k) x^{k}, x^{\overline{n}} = x (x + 1) \dots (x + n - 1)

⟳Expand the rising factorial product; the coefficient of

x^{k}

collects terms picking the "

x

" factor from

k

of the

n

binomials, and the integer products correspond to cycle-counting via the cycle lemma.

x^{\underline{n}} = k = 0 \sum n s (n, k) x^{k}

⟳Replace

x \to - x

in [3] and factor out

(- 1)^{n}

; matching signs forces

s (n, k) = (- 1)^{n - k} c (n, k)

Bell Numbers

The Bell number $B_{n}$ counts all set partitions of $[n]$ regardless of block count:

B_{n} = k = 0 \sum n S (n, k), B_{n + 1} = k = 0 \sum n (k n) B_{k}

⟳First sum is by definition of total partitions; the recurrence classifies partitions by the block containing element

n + 1

, choosing its

k

companions and partitioning the rest.

Integer Partition Function

The partition function $p (n)$ counts the unordered ways to write $n$ as a sum of positive integers (parts). Order does not matter: $4 = 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1$ gives $p (4) = 5$ .

n = 0 \sum \infty p (n) q^{n} = m = 1 \prod \infty \frac{1}{1 - q ^{m}}

⟳Each factor

\frac{1}{1 - q ^{m}} = \sum_{j \geq 0} q^{mj}

chooses how many parts equal

m

; the product over all

m

enumerates every partition exactly once by its part-multiplicities.

Triangular Recurrences

Both Stirling families satisfy Pascal-like recurrences:

S (n, k) = k S (n - 1, k) + S (n - 1, k - 1)

⟳Element

n

either joins one of the

k

existing blocks (

k S (n - 1, k)

) or forms a new singleton block (

S (n - 1, k - 1)

c (n, k) = (n - 1) c (n - 1, k) + c (n - 1, k - 1)

⟳Element

n

either is inserted into one of

n - 1

positions within existing cycles (

(n - 1) c (n - 1, k)

) or starts its own 1-cycle (

c (n - 1, k - 1)

Why It Holds / Derivation

:::proof[Equation [2]: closed form for $S (n, k)$ ] We count surjections $f : [n] ↠ [k]$ in two ways.

Direct via partitions. A surjection is determined by a partition of $[n]$ into $k$ nonempty blocks (the fibers $f^{- 1} (i)$ ) together with a bijection assigning blocks to the $k$ labeled targets. Thus the number of surjections equals $k! S (n, k)$ .

Inclusion–exclusion. Let $A_{i}$ be the set of functions $[n] \to [k]$ that miss target $i$ . The surjections are functions in none of the $A_{i}$ . Total functions number $k^{n}$ . By inclusion–exclusion,

# surjections = j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n},

since choosing

j

forbidden targets leaves

(k - j)^{n}

functions into the remaining

k - j

values.

Equate and solve. Setting $k! S (n, k)$ equal to the inclusion–exclusion sum and dividing by $k!$ yields [2]. $■$

:::proof[Equation [7]: recurrence for $S (n, k)$ ]

Take any partition of $[n]$ into $k$ blocks. Focus on the element $n$ .
Case A — $n$ is alone. Removing the singleton ${n}$ leaves a partition of $[n - 1]$ into $k - 1$ blocks: $S (n - 1, k - 1)$ choices.
Case B — $n$ shares a block. Removing $n$ leaves a partition of $[n - 1]$ into $k$ blocks; conversely $n$ could have been placed in any of these $k$ blocks: $k S (n - 1, k)$ choices.
The cases are disjoint and exhaustive, giving [7]. $■$

James Stirling | 1692–1770

A Scottish mathematician educated at Oxford and Venice, Stirling published Methodus Differentialis (1730), the work that introduced these numbers as coefficients in interpolation series. Though best remembered today for Stirling's approximation $n! \sim 2 π n (n / e)^{n}$ , his deeper contribution was the systematic study of the finite-difference calculus — the algebra of falling factorials in which his namesake numbers naturally appear. His career was marked by political exile (Jacobite associations) and later work managing Scottish mining operations.

Building Intuition

Think of $x^{n}$ and $x^{\underline{k}}$ as two languages for the same combinatorial reality. The "power" language $x^{n}$ counts all functions from an $n$ -set into an $x$ -set — it allows collisions, repetitions, freedom. The "falling factorial" language $x^{\underline{k}}$ counts injections — strict, no collisions. To translate "free" into "strict," you must account for collisions, and that bookkeeping is the Stirling number: $S (n, k)$ tells you how many collision-patterns group your $n$ inputs into $k$ distinct output-classes.

For the first kind, picture writing a permutation in cycle notation. Each permutation of $[n]$ decomposes uniquely into cycles, and $c (n, k)$ simply tallies those with $k$ loops. The recurrence [8] is the act of "inserting the newest dancer" into a circle dance: either you slot them between two existing dancers (anywhere among the $n - 1$ gaps) or you start a brand-new solo circle.

For the integer partition $p (n)$ , abandon labels entirely — the parts are indistinguishable lumps. This loss of structure is exactly why $p (n)$ resists a clean formula while the labeled $S (n, k)$ and $B_{n}$ have tidy ones.

Stirling's triangle for S(n,k): each entry is k·(above) + (above-left)

Worked Examples

Counting surjections with $S(n,k)$

Given: How many ways can 5 distinct toys be distributed to 3 distinct children so that every child gets at least one toy? Steps:

This is the number of surjections $[5] ↠ [3]$ , which equals $3! S (5, 3)$ .
Compute $S (5, 3)$ via formula [2]:

S (5, 3) = \frac{1}{3 !} j = 0 \sum 3 (- 1)^{j} (j 3) (3 - j)^{5} = \frac{1}{6} (3^{5} - 3 \cdot 2^{5} + 3 \cdot 1^{5}) .

Evaluate: $3^{5} = 243$ , $3 \cdot 32 = 96$ , $3 \cdot 1 = 3$ . So $S (5, 3) = \frac{1}{6} (243 - 96 + 3) = \frac{150}{6} = 25.$
Multiply by $3! = 6$ to label the children: $6 \times 25 = 150$ .

Answer:

150 distributions

Bell number and integer partition compared

Given: For

n = 4

, compute (a) the Bell number

B_{4}

(set partitions) and (b) the integer-partition count

p (4)

. Steps (a): Sum the

S (4, k)

row from the triangle:

S (4, 1) + S (4, 2) + S (4, 3) + S (4, 4) = 1 + 7 + 6 + 1 = 15

. So

B_{4} = 15

Check via recurrence [5]: $B_{4} = \sum_{k = 0}^{3} (k 3) B_{k} = (0 3) B_{0} + (1 3) B_{1} + (2 3) B_{2} + (3 3) B_{3} = 1 \cdot 1 + 3 \cdot 1 + 3 \cdot 2 + 1 \cdot 5 = 1 + 3 + 6 + 5 = 15.$ ✓

Steps (b): List partitions of the integer 4 (unlabeled):

4; 3 + 1; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1

. That is 5. Answer:

B_{4} = 15 (labeled set partitions), p (4) = 5 (integer partitions)

The dramatic gap — 15 versus 5 — quantifies how much information labels carry.

Common Misconceptions

Set partitions ≠ integer partitions. The Bell number

B_{n}

counts ways to partition a labeled set

{1, \dots, n}

into blocks; the partition function

p (n)

counts ways to break the integer

n

into summands. They answer entirely different questions and grow at different rates (

B_{n}

super-exponentially,

p (n)

sub-exponentially). Confusing them is the single most common error in this topic. Sign conventions for the first kind differ between texts. Some authors define

s (n, k)

as the signed Stirling number (used in [4]), others reserve

[k n]

for the unsigned count of permutations by cycles. Always verify which family a formula uses; the relation is

s (n, k) = (- 1)^{n - k} [k n]

, so signs alternate down each row. " $S (n, k)$ is symmetric like the binomial coefficient." False. Pascal's triangle is symmetric (

(k n) = (n - k n)

), but Stirling triangles are not. For instance

S (4, 1) = 1

but

S (4, 3) = 6

— no symmetry. The reason: the recurrence [7] has the asymmetric weight

k

on one term, breaking the left–right balance that produces binomial symmetry.

Connections

Stirling numbers are the hinge between several core areas. The change-of-basis equations [1]–[4] connect them to Finite Difference Calculus, where $S (n, k)$ converts ordinary powers into falling factorials that the difference operator $Δ$ treats like derivatives. Their generating functions tie into Exponential Generating Functions: $\sum_{n} S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !}$ and $\sum_{n} B_{n} \frac{x ^{n}}{n !} = e^{e^{x} - 1}$ . The first-kind numbers relate directly to the cycle structure studied in Symmetric Group and to the Gamma Function through rising factorials. The integer partition function $p (n)$ opens into Generating Functions and the deep analytic theory of Modular Forms via Dedekind's eta function.

Real-World Applications

Computer science — Bell numbers in clustering. Counting all possible groupings of $n$ data points equals $B_{n}$ , the size of the search space for partition-based clustering and the number of equivalence relations on a set.
Numerical analysis — Newton forward-difference interpolation. Equation [1] is the engine that rewrites tabulated polynomial data in the falling-factorial basis, the foundation of finite-difference interpolation tables.
Probability — moments of the Poisson distribution. The $n$ -th moment of a Poisson( $λ$ ) variable equals $\sum_{k} S (n, k) λ^{k}$ (Dobinski's formula gives $B_{n}$ at $λ = 1$ ), used in actuarial and queueing models.
Statistical mechanics — counting microstates. Distributing indistinguishable energy quanta among levels uses integer partitions $p (n)$ ; distributing distinguishable particles into occupied states uses Stirling numbers.
Cryptography & combinatorial design — surjection counting. The number of "onto" hash configurations or balanced assignments is $k! S (n, k)$ , used in coupon-collector and load-balancing analyses.
Quantum field theory — normal ordering. Converting between ordinary and normal-ordered products of creation/annihilation operators introduces exactly the Stirling numbers as coefficients (the "Stirling identity for the number operator").
Phylogenetics — counting tree topologies and labelings. Partition structures and Bell numbers enumerate possible ancestral groupings of species.

Historical Development

1730 — James Stirling publishes Methodus Differentialis, introducing both families as interpolation coefficients.
1740s — Leonhard Euler studies the generating function $\prod (1 - q^{m})^{- 1}$ for $p (n)$ and proves the celebrated pentagonal number theorem, giving a fast recurrence for partitions.
1859 — G. Dobinski derives his formula $B_{n} = \frac{1}{e} \sum_{k \geq 0} \frac{k ^{n}}{k !}$ , expressing Bell numbers as a Poisson moment.
1877 — The cycle interpretation of first-kind numbers is clarified within the developing theory of permutation groups.
1918 — G. H. Hardy and Srinivasa Ramanujan establish the asymptotic formula for $p (n)$ via the circle method, a landmark of analytic number theory.
1934 — Eric Temple Bell systematizes the numbers now bearing his name in his paper on "exponential polynomials."
1937 — Hans Rademacher converts the Hardy–Ramanujan asymptotic into an exact convergent series for $p (n)$ .
1974 — Knuth, Graham, and Patashnik later popularize the bracket/brace notation $[k n]$ , ${k n}$ in Concrete Mathematics, unifying the field's conventions.
2011 — Ken Ono and collaborators discover that partition numbers exhibit fractal congruence structure governed by modular forms, vindicating Ramanujan's mysterious congruences $p (5 n + 4) \equiv 0 (mod 5)$ .

Subtleties & Limits

While $S (n, k)$ and $B_{n}$ have explicit closed forms, the integer partition function $p (n)$ does not — Rademacher's exact formula is an infinite convergent series, not a finite expression. Ramanujan's congruences ( $p (5 n + 4) \equiv 0 (mod 5)$ , $p (7 n + 5) \equiv 0 (mod 7)$ , $p (11 n + 6) \equiv 0 (mod 11)$ ) are now understood via modular forms, yet a full classification of all such congruences, and a transparent combinatorial (bijective) explanation of even the mod-5 case, remains an active research frontier. The deep mystery is why a purely additive counting problem should be controlled by the symmetry-rich world of modular forms — a connection still being mined.