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).
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 ) | = ( − 1 ) n − k s ( n , k ) . {\displaystyle {\biggl [}{n \atop k}{\biggr ]}=c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k)\,.}
Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets:
S ( n , k ) = { n k } = S n ( k ) . {\displaystyle S(n,k)={\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}=S_{n}^{(k)}\,.}
Abramowitz and Stegun use an uppercase S {\displaystyle S} and a blackletter S {\displaystyle {\mathfrak {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, 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. Another, infrequent notation is s 1 ( n , k ) {\displaystyle s_{1}(n,k)} and s 2 ( n , k ) {\displaystyle s_{2}(n,k)} .
Expansions of falling and rising factorials Stirling numbers express coefficients in expansions of falling and rising factorials as polynomials. That is, the falling factorial, defined as ( x ) n = x ( x − 1 ) ⋯ ( x − n + 1 ) , {\displaystyle \ (x)_{n}=x(x-1)\ \cdots (x-n+1)\ ,} is a polynomial in x of degree n whose expansion is
( x ) n = ∑ k = 0 n s ( n , k ) x k {\displaystyle (x)_{n}\ =\ \sum _{k=0}^{n}\ s(n,k)\ x^{k}\ }
… excerpt ends here. Continue reading the full article.
