Stirling Numbers and Partition Functions

⚡ Key Takeaways

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.

💡 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.

DefinitionStirling Numbers of the Second Kind

$S(n,k)$ (also written $\left\{ {n \atop k} \right\}$ ) 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$ .

1

\quad x^n = \sum_{k=0}^{n} S(n,k)\, x^{\underline{k}}, \qquad x^{\underline{k}} = x(x-1)\cdots(x-k+1)

Derivation hint: Count functions from $[n]$ to $[x]$ two ways — total functions give $x^n$ ; classify by the image of size $k$ , choose the image ( $\binom{x}{k}k!$ as $x^{\underline k}$ ) and partition the domain ( $S(n,k)$ ).

2

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

Derivation hint: 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.

DefinitionStirling Numbers of the First Kind

The unsigned Stirling numbers of the first kind $c(n,k) = \left[ {n \atop k} \right]$ 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.

3

\quad x^{\overline{n}} = \sum_{k=0}^{n} c(n,k)\, x^{k}, \qquad x^{\overline{n}} = x(x+1)\cdots(x+n-1)

Derivation hint: 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.

4

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

Derivation hint: Replace $x \to -x$ in [3] and factor out $(-1)^n$ ; matching signs forces $s(n,k)=(-1)^{n-k}c(n,k)$ .

DefinitionBell Numbers

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

5

\quad B_n = \sum_{k=0}^{n} S(n,k), \qquad B_{n+1} = \sum_{k=0}^{n}\binom{n}{k}B_k

Derivation hint: 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.

DefinitionInteger 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$ .

6

\quad \sum_{n=0}^{\infty} p(n)\,q^{n} = \prod_{m=1}^{\infty} \frac{1}{1-q^{m}}

Derivation hint: Each factor $\frac{1}{1-q^m}=\sum_{j\ge 0}q^{mj}$ chooses how many parts equal $m$ ; the product over all $m$ enumerates every partition exactly once by its part-multiplicities.

TheoremTriangular Recurrences

Both Stirling families satisfy Pascal-like recurrences:

7

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

Derivation hint: 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)$ ).

8

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

Derivation hint: 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)$ ).

JS

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\sqrt{2\pi 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.

🧠 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.

Figure

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

ExampleCounting 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: 1. This is the number of surjections $[5]\twoheadrightarrow[3]$ , which equals $3!\,S(5,3)$ . 2. Compute $S(5,3)$ via formula [2]:

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

3. 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.$ 4. Multiply by $3!=6$ to label the children: $6\times 25 = 150$ .

Answer:

\boxed{150 \text{ distributions}}

ExampleBell 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}\binom{3}{k}B_k = \binom30 B_0+\binom31 B_1+\binom32 B_2+\binom33 B_3 = 1\cdot1 + 3\cdot1 + 3\cdot2 + 1\cdot5 = 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:

\boxed{B_4 = 15 \text{ (labeled set partitions)}, \qquad p(4) = 5 \text{ (integer partitions)}}

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

⚠️ Common mistake

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.

⚠️ Common mistake

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 $\left[{n\atop k}\right]$ for the unsigned count of permutations by cycles. Always verify which family a formula uses; the relation is $s(n,k)=(-1)^{n-k}\left[{n\atop k}\right]$ , so signs alternate down each row.

Counterexample

" $S(n,k)$ is symmetric like the binomial coefficient." False. Pascal's triangle is symmetric ( $\binom nk = \binom{n}{n-k}$ ), 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.

connection

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 $\Delta$ 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.

🔬 Where this appears

⏳ History

- 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=\frac1e\sum_{k\ge0}\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

\left[{n\atop k}\right]

,

\left\{{n\atop k}\right\}

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(5n+4)\equiv 0\ (\mathrm{mod}\ 5)

.

open-problem

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(5n+4)\equiv0\pmod 5$ , $p(7n+5)\equiv0\pmod 7$ , $p(11n+6)\equiv0\pmod{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.

Stirling Numbers and Partition Functions

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also