Stirling number
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems.
They are named after James Stirling, who introduced them in the 18th century.
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, with different ways of counting orderings within each subset.
Notation
Main article: Stirling numbers of the first kind
Main article: Stirling numbers of the second kind
Several different notations for Stirling numbers are in use.
Common notations are:
for unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles,
for ordinary (signed) Stirling numbers of the first kind, and
for Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets.
Abramowitz and Stegun use an uppercase S and a blackletter S, 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.
(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.
Expansions of falling and rising factorials
Stirling numbers express coefficients in expansions of falling and rising factorials (also known as the Pochhammer symbol) as polynomials.
with (signed) Stirling numbers of the first kind as coefficients.
Stirling numbers of the second kind express reverse relations:
and
As change of basis coefficients
Considering the set of polynomials in the (indeterminate) variable x as a vector space, each of the three sequences
As inverse matrices
The Stirling numbers of the first and second kinds can be considered inverses of one another:
and
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.
Example
Expressing a polynomial in the basis of falling factorials is useful for calculating sums of the polynomial evaluated at consecutive integers.
Indeed, the sum of a falling factorial is simply expressed as another falling factorial (for k≠-1)
For example, the sum of fourth powers of integers up to n (this time with n included), is:
Here the Stirling numbers can be computed from their definition as the number of partitions of 4 elements into k non-empty unlabeled subsets.
Lah numbers
Main article: Lah numbers
These numbers are coefficients expressing falling factorials in terms of rising factorials and vice versa:
Symmetric formulae
Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind.
and
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:
| kn | −1 | −2 | −3 | −4 | −5 |
|---|---|---|---|---|---|
| −1 | 1 | 1 | 1 | 1 | 1 |
| −2 | 0 | 1 | 3 | 7 | 15 |
| −3 | 0 | 0 | 1 | 6 | 25 |
| −4 | 0 | 0 | 0 | 1 | 10 |
| −5 | 0 | 0 | 0 | 0 | 1 |
See also
- Bell polynomials
- Catalan number
- Cycles and fixed points
- Lah number
- Pochhammer symbol
- Polynomial sequence
- Stirling transform
- Touchard polynomials
Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Stirling number.