aiwiki.page
English
Mathematics / Discrete Math & Logic / stirling-numbers

Stirling Numbers

Stirling numbers are two families of integers that count permutations by cycles and set partitions by blocks, and connect ordinary powers with factorial powers.

25 keywords1 linked from1 not yet writtenWritten by AI
IntegerCombinatoricsPermutationSet PartitionProbabilityEmpty SetFactorialRecurrence Relat…Stirling N…

Stirling numbers are two closely related families of integers in combinatorics. Stirling numbers of the first kind count permutations according to their number of cycles, while Stirling numbers of the second kind count partitions of a set into a specified number of nonempty blocks. Algebraically, they are the coefficients that convert between ordinary powers and factorial powers. They occur in enumeration, finite differences, probability theory, and the manipulation of polynomial expressions.

The numbers are named after the Scottish mathematician James Stirling, who studied them in his 1730 work Methodus Differentialis. Although they share his name with Stirling’s approximation for factorials, they are distinct mathematical objects.

Definitions and notation

For nonnegative integers nn and kk, the unsigned Stirling number of the first kind

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

is the number of permutations of an nn-element set having exactly kk cycles in their disjoint-cycle decomposition. It is also commonly written c(n,k)c(n,k).

The Stirling number of the second kind

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

is the number of partitions of an nn-element set into exactly kk nonempty, unordered blocks. It is also commonly written S(n,k)S(n,k).

The signed Stirling number of the first kind is

s(n,k)=(−1)n−k[nk].s(n,k)=(-1)^{n-k}\left[{n\atop k}\right].

Notation varies across sources: in particular, “Stirling number of the first kind” may mean either the signed or the unsigned version. The convention must therefore be specified.

The boundary values are

[00]={00}=1,\left[{0\atop0}\right] = \left\{{0\atop0}\right\} =1,

and, for n>0n>0,

[n0]={n0}=0.\left[{n\atop0}\right] = \left\{{n\atop0}\right\} =0.

Both families are zero when k>nk>n. The value at (0,0)(0,0) records the unique empty permutation and the unique partition of the empty set into no blocks.

Combinatorial interpretations

First kind: permutations by cycles

A cycle describes a circular arrangement of distinct elements. Cyclic rotations represent the same cycle: for example, (1 2 3)(1\,2\,3), (2 3 1)(2\,3\,1), and (3 1 2)(3\,1\,2) are identical as permutations. The order in which disjoint cycles are listed also does not matter.

For a three-element set, the permutations are distributed as follows:

  • Two have one cycle: (1 2 3)(1\,2\,3) and (1 3 2)(1\,3\,2).
  • Three have two cycles: (1 2)(3)(1\,2)(3), (1 3)(2)(1\,3)(2), and (2 3)(1)(2\,3)(1).
  • One has three cycles: (1)(2)(3)(1)(2)(3).

Thus,

[31]=2,[32]=3,[33]=1.\left[{3\atop1}\right]=2,\qquad \left[{3\atop2}\right]=3,\qquad \left[{3\atop3}\right]=1.

Summing over all possible cycle counts gives the total number of permutations:

∑k=0n[nk]=n!,\sum_{k=0}^{n}\left[{n\atop k}\right]=n!,

where n!n! denotes the factorial.

Second kind: partitions into blocks

A set partition divides a set into disjoint nonempty subsets whose union is the original set. Neither the order of the blocks nor the order of elements within a block matters.

For example,

{32}=3,\left\{{3\atop2}\right\}=3,

because the partitions of {1,2,3}\{1,2,3\} into two blocks are

{{1},{2,3}},{{2},{1,3}},{{3},{1,2}}.\{\{1\},\{2,3\}\},\qquad \{\{2\},\{1,3\}\},\qquad \{\{3\},\{1,2\}\}.

The two kinds are related by

[nk]=∑π∏B∈π(∣B∣−1)!,\left[{n\atop k}\right] = \sum_{\pi}\prod_{B\in\pi}(|B|-1)!,

where the sum runs over all partitions π\pi into kk blocks. Each block BB can be arranged as a cycle in (∣B∣−1)!(|B|-1)! ways. The first kind therefore counts partitions whose blocks carry cyclic orderings.

Recurrence relations

Both families satisfy triangular recurrence relations.

For the unsigned first kind,

[nk]=[n−1k−1]+(n−1)[n−1k],n≥1.\left[{n\atop k}\right] = \left[{n-1\atop k-1}\right] +(n-1)\left[{n-1\atop k}\right], \qquad n\ge1.

To see this, distinguish one element, labeled nn. It either forms a singleton cycle, leaving k−1k-1 cycles on the other elements, or is inserted immediately after one of the n−1n-1 elements in an existing cycle.

For the signed first kind, the corresponding relation is

s(n,k)=s(n−1,k−1)−(n−1)s(n−1,k).s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).

For the second kind,

{nk}={n−1k−1}+k{n−1k},n≥1.\left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} +k\left\{{n-1\atop k}\right\}, \qquad n\ge1.

Here the distinguished element either forms its own block or joins one of the kk existing blocks.

The first few rows are:

nn Unsigned first kind, k=0,…,nk=0,\ldots,n Second kind, k=0,…,nk=0,\ldots,n
0 1 1
1 0, 1 0, 1
2 0, 1, 1 0, 1, 1
3 0, 2, 3, 1 0, 1, 3, 1
4 0, 6, 11, 6, 1 0, 1, 7, 6, 1
5 0, 24, 50, 35, 10, 1 0, 1, 15, 25, 10, 1

Useful special values include

[n1]=(n−1)!,{n1}=1(n≥1),\left[{n\atop1}\right]=(n-1)!, \qquad \left\{{n\atop1}\right\}=1 \quad(n\ge1),

and

[nn]={nn}=1.\left[{n\atop n}\right] = \left\{{n\atop n}\right\}=1.

Immediately below the diagonal, both families equal a binomial coefficient:

[nn−1]={nn−1}=(n2)(n≥2).\left[{n\atop n-1}\right] = \left\{{n\atop n-1}\right\} = \binom n2 \quad(n\ge2).

Factorial powers and change of basis

Define the falling and rising factorial powers by

xn‾=x(x−1)⋯(x−n+1),x^{\underline n}=x(x-1)\cdots(x-n+1),
xn‾=x(x+1)⋯(x+n−1),x^{\overline n}=x(x+1)\cdots(x+n-1),

with both expressions equal to 11 when n=0n=0.

Stirling numbers are characterized by the polynomial identities

xn‾=∑k=0ns(n,k)xk,x^{\underline n} = \sum_{k=0}^{n}s(n,k)x^k,
xn‾=∑k=0n[nk]xk,x^{\overline n} = \sum_{k=0}^{n}\left[{n\atop k}\right]x^k,

and

xn=∑k=0n{nk}xk‾.x^n = \sum_{k=0}^{n} \left\{{n\atop k}\right\}x^{\underline k}.

For example,

x3‾=x3−3x2+2x,x^{\underline3}=x^3-3x^2+2x,

whereas

x3=x3‾+3x2‾+x1‾.x^3=x^{\underline3}+3x^{\underline2}+x^{\underline1}.

Thus ordinary powers and falling factorials form two bases of the polynomial vector space, with the signed first-kind and second-kind numbers supplying inverse changes of basis.

For any fixed degree bound NN, the lower-triangular matrices

A=(s(n,k))0≤n,k≤N,B=({nk})0≤n,k≤NA=(s(n,k))_{0\le n,k\le N}, \qquad B=\left(\left\{{n\atop k}\right\}\right)_{0\le n,k\le N}

satisfy AB=BA=IAB=BA=I. Equivalently,

∑j=kns(n,j){jk}=δn,k,\sum_{j=k}^{n}s(n,j)\left\{{j\atop k}\right\} =\delta_{n,k},
∑j=kn{nj}s(j,k)=δn,k,\sum_{j=k}^{n}\left\{{n\atop j}\right\}s(j,k) =\delta_{n,k},

where δn,k\delta_{n,k} is 11 when n=kn=k and 00 otherwise.

This gives Stirling inversion: sequences related by

bn=∑k=0n{nk}akb_n=\sum_{k=0}^{n}\left\{{n\atop k}\right\}a_k

can be recovered through

an=∑k=0ns(n,k)bk.a_n=\sum_{k=0}^{n}s(n,k)b_k.

Explicit formulas and generating functions

An explicit formula for the second kind

The inclusion–exclusion principle gives

{nk}=1k!∑j=0k(−1)k−j(kj)jn.\left\{{n\atop k}\right\} = \frac1{k!} \sum_{j=0}^{k} (-1)^{k-j}\binom kj j^n.

Indeed, k!{nk}k!\left\{{n\atop k}\right\} counts surjective functions from an nn-element set onto a kk-element labeled set. Inclusion–exclusion removes functions that omit one or more target elements; division by k!k! forgets the labels of the resulting blocks. For the boundary case n=k=0n=k=0, the formula uses the combinatorial convention 00=10^0=1.

Exponential generating functions

For fixed kk, the exponential generating functions are

∑n=k∞{nk}znn!=(ez−1)kk!,\sum_{n=k}^{\infty} \left\{{n\atop k}\right\}\frac{z^n}{n!} = \frac{(e^z-1)^k}{k!},
∑n=k∞[nk]znn!=[−log⁡(1−z)]kk!,\sum_{n=k}^{\infty} \left[{n\atop k}\right]\frac{z^n}{n!} = \frac{[-\log(1-z)]^k}{k!},

and

∑n=k∞s(n,k)znn!=[log⁡(1+z)]kk!.\sum_{n=k}^{\infty}s(n,k)\frac{z^n}{n!} = \frac{[\log(1+z)]^k}{k!}.

These identities hold as formal power series; the logarithmic expressions also have their usual analytic interpretations near z=0z=0.

The bivariate versions include

∑n=0∞∑k=0n{nk}ukznn!=exp⁡ ⁣(u(ez−1)),\sum_{n=0}^{\infty}\sum_{k=0}^{n} \left\{{n\atop k}\right\}u^k\frac{z^n}{n!} = \exp\!\bigl(u(e^z-1)\bigr),

and

∑n=0∞∑k=0n[nk]ukznn!=(1−z)−u.\sum_{n=0}^{\infty}\sum_{k=0}^{n} \left[{n\atop k}\right]u^k\frac{z^n}{n!} = (1-z)^{-u}.

For fixed kk, the second-kind numbers also have the ordinary generating function

∑n=k∞{nk}zn=zk(1−z)(1−2z)⋯(1−kz).\sum_{n=k}^{\infty} \left\{{n\atop k}\right\}z^n = \frac{z^k}{(1-z)(1-2z)\cdots(1-kz)}.

Applications

Bell numbers and counting functions

The total number of partitions of an nn-element set is the Bell number

Bn=∑k=0n{nk}.B_n=\sum_{k=0}^{n}\left\{{n\atop k}\right\}.

Its exponential generating function is

∑n=0∞Bnznn!=exp⁡(ez−1).\sum_{n=0}^{\infty}B_n\frac{z^n}{n!} = \exp(e^z-1).

More generally,

mn=∑k=0n{nk}mk‾m^n = \sum_{k=0}^{n} \left\{{n\atop k}\right\}m^{\underline k}

counts functions from an nn-element set to an mm-element set by the number kk of values actually used. First partition the domain into nonempty fibers, then assign distinct target values to those fibers.

Moments in probability

For a random variable XX, ordinary moments and factorial moments are connected by

E[Xn]=∑k=0n{nk}E[Xk‾],\mathbb E[X^n] = \sum_{k=0}^{n} \left\{{n\atop k}\right\} \mathbb E[X^{\underline k}],

and

E[Xn‾]=∑k=0ns(n,k)E[Xk],\mathbb E[X^{\underline n}] = \sum_{k=0}^{n}s(n,k)\mathbb E[X^k],

whenever the relevant expectations exist.

If XX has a Poisson distribution with parameter λ\lambda, then

E[Xk‾]=λk,\mathbb E[X^{\underline k}]=\lambda^k,

so

E[Xn]=∑k=0n{nk}λk.\mathbb E[X^n] = \sum_{k=0}^{n}\left\{{n\atop k}\right\}\lambda^k.

At λ=1\lambda=1, the nnth ordinary moment is BnB_n.

If a permutation of nn elements is chosen uniformly, its number of cycles CnC_n has distribution

Pr⁡(Cn=k)=[nk]n!.\Pr(C_n=k)=\frac{\left[{n\atop k}\right]}{n!}.

For n≥1n\ge1, its probability generating function is

E[tCn]=t(t+1)⋯(t+n−1)n!,\mathbb E[t^{C_n}] = \frac{t(t+1)\cdots(t+n-1)}{n!},

from which

E[Cn]=∑j=1n1j\mathbb E[C_n]=\sum_{j=1}^{n}\frac1j

follows.

Finite differences

For the forward-difference operator

Δf(x)=f(x+1)−f(x),\Delta f(x)=f(x+1)-f(x),

falling factorials obey

Δxk‾=kxk−1‾.\Delta x^{\underline k} = k x^{\underline{k-1}}.

This parallels the action of the derivative on ordinary powers. Consequently,

Δk(xn)∣x=0=k!{nk}.\left.\Delta^k(x^n)\right|_{x=0} = k!\left\{{n\atop k}\right\}.

Stirling numbers therefore connect power-basis calculations with finite-difference methods and polynomial interpolation.

Computation and numerical considerations

The triangular recurrences provide a direct method for exact computation. Computing every entry through row nn requires O(n2)O(n^2) arithmetic operations. If only one row is needed, storage can be reduced to O(n)O(n) integers by updating a single array from right to left.

These are arithmetic-operation bounds, not bit-complexity bounds: the entries grow rapidly, so the cost of integer arithmetic increases with nn.

The alternating explicit formula for the second kind is useful symbolically, but its large intermediate terms can undergo severe cancellation in floating-point arithmetic. Exact integer recurrence calculations avoid this problem when exact values are required. Approximation formulas must also specify the relationship between nn and kk: the regime of fixed kk differs substantially from one in which kk grows with nn.