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 a purely algebraic setting in his book Methodus differentialis (1730).

[1] They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

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

Ordinary (signed) Stirling numbers of the first kind are commonly denoted: Unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles, are denoted: Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets:[3] Abramowitz and Stegun use an uppercase

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.

[4] 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.

Stirling numbers express coefficients in expansions of falling and rising factorials (also known as the Pochhammer symbol) as polynomials.

is a polynomial in x of degree n whose expansion is with (signed) Stirling numbers of the first kind as coefficients.

is a polynomial in x of degree n whose expansion is with unsigned Stirling numbers of the first kind as coefficients.

Stirling numbers of the second kind express the reverse relations: and Considering the set of polynomials in the (indeterminate) variable x as a vector space, each of the three sequences is a basis.

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

Falling factorials define, up to scaling, the same polynomials as binomial coefficients:

are thus described by similar formulas: Expressing a polynomial in the basis of falling factorials is useful for calculating sums of the polynomial evaluated at consecutive integers.

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.

in the standard basis is given by Faulhaber's formula, which in general is more complicated.

The Stirling numbers of the first and second kinds can be considered inverses of one another: and where

Symbolically, this is written 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.

These numbers are coefficients expressing falling factorials in terms of rising factorials and vice versa: As above, this means they express the change of basis between the bases

In particular, one formula is the inverse of the other, thus: Similarly, composing the change of basis from

, related by a finite sum Stirling number formula given by for all integers

Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind.

[9] and The Stirling numbers can be extended to negative integral values, but not all authors do so in the same way.

[10][11][12] Regardless of the approach taken, it is worth noting that Stirling numbers of first and second kind are connected by the relations: when n and k are nonnegative integers.

: Donald Knuth[12] defined the more general Stirling numbers by extending a recurrence relation to all integers.

are zero if n is negative and k is nonnegative, or if n is nonnegative and k is negative, and so we have, for any integers n and k, On the other hand, for positive integers n and k, David Branson[11] defined

In this approach, one has the following extension of the recurrence relation of the Stirling numbers of the first kind: For example,