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 and , the unsigned Stirling number of the first kind
is the number of permutations of an -element set having exactly cycles in their disjoint-cycle decomposition. It is also commonly written .
The Stirling number of the second kind
is the number of partitions of an -element set into exactly nonempty, unordered blocks. It is also commonly written .
The signed Stirling number of the first kind is
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
and, for ,
Both families are zero when . The value at 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, , , and 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: and .
- Three have two cycles: , , and .
- One has three cycles: .
Thus,
Summing over all possible cycle counts gives the total number of permutations:
where 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,
because the partitions of into two blocks are
The two kinds are related by
where the sum runs over all partitions into blocks. Each block can be arranged as a cycle in 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,
To see this, distinguish one element, labeled . It either forms a singleton cycle, leaving cycles on the other elements, or is inserted immediately after one of the elements in an existing cycle.
For the signed first kind, the corresponding relation is
For the second kind,
Here the distinguished element either forms its own block or joins one of the existing blocks.
The first few rows are:
| Unsigned first kind, | Second kind, | |
|---|---|---|
| 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
and
Immediately below the diagonal, both families equal a binomial coefficient:
Factorial powers and change of basis
Define the falling and rising factorial powers by
with both expressions equal to when .
Stirling numbers are characterized by the polynomial identities
and
For example,
whereas
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 , the lower-triangular matrices
satisfy . Equivalently,
where is when and otherwise.
This gives Stirling inversion: sequences related by
can be recovered through
Explicit formulas and generating functions
An explicit formula for the second kind
The inclusion–exclusion principle gives
Indeed, counts surjective functions from an -element set onto a -element labeled set. Inclusion–exclusion removes functions that omit one or more target elements; division by forgets the labels of the resulting blocks. For the boundary case , the formula uses the combinatorial convention .
Exponential generating functions
For fixed , the exponential generating functions are
and
These identities hold as formal power series; the logarithmic expressions also have their usual analytic interpretations near .
The bivariate versions include
and
For fixed , the second-kind numbers also have the ordinary generating function
Applications
Bell numbers and counting functions
The total number of partitions of an -element set is the Bell number
Its exponential generating function is
More generally,
counts functions from an -element set to an -element set by the number 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 , ordinary moments and factorial moments are connected by
and
whenever the relevant expectations exist.
If has a Poisson distribution with parameter , then
so
At , the th ordinary moment is .
If a permutation of elements is chosen uniformly, its number of cycles has distribution
For , its probability generating function is
from which
follows.
Finite differences
For the forward-difference operator
falling factorials obey
This parallels the action of the derivative on ordinary powers. Consequently,
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 requires arithmetic operations. If only one row is needed, storage can be reduced to 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 .
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 and : the regime of fixed differs substantially from one in which grows with .