In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in his 1782 Sanpō-Gakkai (The Sea of Learning on Mathematics).
Article
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in his 1782 Sanpō-Gakkai (The Sea of Learning on Mathematics).
Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind. Additionally, Lah numbers are sometimes referred to as Stirling numbers of the third kind. Each kind is detailed in its respective article, this one serving as a description of relations between them.
A common property of all three kinds is that they describe coefficients relating three different sequences of polynomials that frequently arise in combinatorics. Moreover, all three can be defined as the number of partitions of n elements into k non-empty subsets, where each subset is endowed with a certain kind of order (no order, cyclical, or linear).
Contents
Notation
Several different notations for Stirling numbers are in use. Ordinary (signed) Stirling numbers of the first kind are commonly denoted by
s
(
n
,
k
)
.
{\displaystyle s(n,k)\,.}
Unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles, are denoted by
[
n
k
]
=
c
(
n
,
k
)
=
|
s
(
n
,
k
)
|
=
(
−
Expansions of falling and rising factorials
Stirling numbers express coefficients in expansions of falling and rising factorials as polynomials.
Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind.
[
n
k
]
=
∑
j
=
n
2
n
−
k
(
−
1
)
j
−
k
(
j
−
1
k
−
1
)
(
2
n
−
k
j
)
Stirling numbers with negative integral values
The Stirling numbers can be extended to negative integral values, but not all authors do so in the same way. Regardless of the approach taken, it is worth noting that Stirling numbers of first and second kind are connected by the relations:
, respectively, for the first and second kinds of Stirling number. The notation of brackets and braces, in analogy to binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth, though the bracket notation conflicts with a common notation for Gaussian coefficients. The mathematical motivation for this type of notation, as well as additional Stirling number formulae, may be found on the page for Stirling numbers and exponential generating functions.
with (signed) Stirling numbers of the first kind as coefficients.
Note that
(
x
)
0
≡
1
,
{\displaystyle \ (x)_{0}\equiv 1\ ,}
by convention, because it is an empty product. The notations
x
n
_
{\displaystyle \ x^{\underline {n}}\ }
for the falling factorial and
x
n
¯
{\displaystyle \ x^{\overline {n}}\ }
for the rising factorial are also often used. (Confusingly, the Pochhammer symbol that many use for falling factorials is used in special functions for rising factorials.)
The above relations then express the change of basis between them, as summarized in the following commutative diagram:
The coefficients for the two bottom changes are described by the Lah numbers below.
Since coefficients in any basis are unique, one can define Stirling numbers this way, as the coefficients expressing polynomials of one basis in terms of another, that is, the unique numbers relating
x
n
{\displaystyle x^{n}}
with falling and rising factorials as above.
Falling factorials define, up to scaling, the same polynomials as binomial coefficients:
is the Kronecker delta. These two relationships may be understood to be matrix inverse relationships. That is, let s be the lower triangular matrix of Stirling numbers of the first kind, whose matrix elements
s
n
k
=
s
(
n
,
k
)
.
{\displaystyle s_{nk}=s(n,k).\,}
The inverse of this matrix is S, the lower triangular matrix of Stirling numbers of the second kind, whose entries are
S
n
k
=
S
(
n
,
k
)
.
{\displaystyle S_{nk}=S(n,k).}
Symbolically, this is written
s
−
1
=
S
{\displaystyle s^{-1}=S\,}
Although s and S are infinite, so calculating a product entry involves an infinite sum, the matrix multiplications work because these matrices are lower triangular, so only a finite number of terms in the sum are nonzero.
n
,
k
)
=
0
{\displaystyle L(n,k)=0}
if
n
<
k
{\displaystyle n<k}
or
k
=
0
<
n
{\displaystyle k=0<n}
.
These numbers are coefficients expressing falling factorials in terms of rising factorials and vice versa:
can be defined as the number of partitions of n elements into k non-empty unlabeled subsets, where each subset is endowed with no order, a cyclic order, or a linear order, respectively. In particular, this implies the inequalities:
These inversion relations between the two sequences translate into functional equations between the sequence exponential generating functions given by the Stirling (generating function) transform as
