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

Main articles: Stirling numbers of the first kind and Stirling numbers of the second kind

Several different notations for Stirling numbers are in use. Ordinary (signed) Stirling numbers of the first kind are commonly denoted by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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

${\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)={\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}=S_{n}^{(k)}\,.$

Abramowitz and Stegun use an uppercase $S$ and a blackletter ${\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)$ and $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)\ \cdots (x-n+1)\ ,$ is a polynomial in x of degree n whose expansion is

$(x)_{n}\ =\ \sum _{k=0}^{n}\ s(n,k)\ x^{k}\$

with (signed) Stirling numbers of the first kind as coefficients.

Note that $\ (x)_{0}\equiv 1\ ,$ by convention, because it is an empty product. The notations $\ x^{\underline {n}}\$ for the falling factorial and $\ 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.)

Similarly, the rising factorial, defined as $\ x^{(n)}\ =\ x(x+1)\ \cdots (x+n-1)\ ,$ is a polynomial in x of degree n whose expansion is

$x^{(n)}\ =\ \sum _{k=0}^{n}\ {\biggl [}{n \atop k}{\biggr ]}\ x^{k}\ =\ \sum _{k=0}^{n}\ (-1)^{n-k}\ s(n,k)\ x^{k}\ ,$

with unsigned Stirling numbers of the first kind as coefficients. One of these expansions can be derived from the other by observing that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^{(n)} = (-1)^n (-x)_{n} ~.}

Stirling numbers of the second kind express the reverse relations:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^n\ =\ \sum_{k=0}^n\ S(n,k)\ (x)_k\ }

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^n\ =\ \sum_{k=0}^n\ (-1)^{n-k}\ S(n,k)\ x^{(k)} ~.}

As change of basis coefficients

Considering the set of polynomials in the (indeterminate) variable x as a vector space, each of the three sequences

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^0,x^1,x^2,x^3,\dots \quad (x)_0,(x)_1,(x)_2,\dots \quad x^{(0)},x^{(1)},x^{(2)},\dots}

is a basis. That is, every polynomial in x can be written as a sum Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 x^{(0)} + a_1 x^{(1)} + \dots + a_n x^{(n)}} for some unique coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} (similarly for the other two bases). The above relations then express the change of basis between them, as summarized in the following commutative diagram:

Template:Dark mode invert

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} with falling and rising factorials as above.

Falling factorials define, up to scaling, the same polynomials as binomial coefficients: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \binom{x}{k} = (x)_k/k!} . The changes between the standard basis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle x^0, x^1, x^2, \dots} and the basis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \binom{x}{0}, \binom{x}{1}, \binom{x}{2}, \dots} are thus described by similar formulas:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n=\sum_{k=0}^n \biggl\{{\!n\! \atop \!k\!}\biggr\} k! \binom{x}{k} \quad \text{and} \quad \binom{x}{n}=\sum_{k=0}^n \frac{s(n,k)}{n!} x^k} .

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 falling factorials with fixed k can be expressed as another falling factorial (for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\ne-1} )

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{0\leq i < n} (i)_k = \frac{(n)_{k+1}}{k+1} }

This can be proved by induction.

For example, the sum of fourth powers of integers up to n (this time with n included), is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \sum_{i=0}^{n} i^4 & = \sum_{i=0}^n \sum_{k=0}^4 \biggl\{{\!4\! \atop \!k\!}\biggr\} (i)_k = \sum_{k=0}^4 \biggl\{{\!4\! \atop \!k\!}\biggr\} \sum_{i=0}^n (i)_k = \sum_{k=0}^4 \biggl\{{\!4\! \atop \!k\!}\biggr\} \frac{(n{+}1)_{k+1}}{k{+}1} \\[10mu] & = \biggl\{{\!4\! \atop \!1\!}\biggr\} \frac{(n{+}1)_{2}}2 + \biggl\{{\!4\! \atop \!2\!}\biggr\} \frac{(n{+}1)_{3}}3 + \biggl\{{\!4\! \atop \!3\!}\biggr\} \frac{(n{+}1)_{4}}4 + \biggl\{{\!4\! \atop \!4\!}\biggr\} \frac{(n{+}1)_{5}}5 \\[8mu] & = \frac12 (n{+}1)_{2} + \frac73 (n{+}1)_{3} + \frac64 (n{+}1)_{4} + \frac15 (n{+}1)_{5}\,. \end{align}}

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 contrast, the sum Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \sum_{i=0}^n i^k} in the standard basis is given by Faulhaber's formula, which in general is more complicated.

As inverse matrices

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j=k}^n s(n,j) S(j,k) = \sum_{j=k}^n (-1)^{n-j} \biggl[{n \atop j}\biggr] \biggl\{{\!j\! \atop \!k\!}\biggr\} = \delta_{n,k}}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j=k}^n S(n,j) s(j,k) = \sum_{j=k}^n (-1)^{j-k} \biggl\{{\!n\! \atop \!j\!}\biggr\} \biggl[{j \atop k}\biggr]= \delta_{n,k},}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_{nk}} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{nk}=S(n,k).} Symbolically, this is written

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.

Lah numbers

Main article: Lah numbers

The Lah numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}} are sometimes called Stirling numbers of the third kind. By convention, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(0,0)=1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(n,k)=0} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n<k} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 0 < n} .

These numbers are coefficients expressing falling factorials in terms of rising factorials and vice versa:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(n)} = \sum_{k=0}^n L(n,k) (x)_k\quad} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad(x)_n = \sum_{k=0}^n (-1)^{n-k} L(n,k)x^{(k)}.}

As above, this means they express the change of basis between the bases Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x)_0,(x)_1,(x)_2,\cdots} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(0)},x^{(1)},x^{(2)},\cdots} , completing the diagram. In particular, one formula is the inverse of the other, thus:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j=k}^n (-1)^{j-k} L(n,j) L(j,k) = \delta_{n,k}.}

Similarly, composing the change of basis from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(n)}} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} with the change of basis from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x)_{n}} gives the change of basis directly from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(n)}} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x)_{n}} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(n,k) = \sum_{j=k}^n \biggl[{n \atop j}\biggr] \biggl\{{\!j\! \atop \!k\!}\biggr\} ,}

and similarly for other compositions. In terms of matrices, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} denotes the matrix with entries Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{nk}=L(n,k)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L^{-}} denotes the matrix with entries Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L^{-}_{nk}=(-1)^{n-k}L(n,k)} , then one is the inverse of the other: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L^{-} = L^{-1}} . Composing the matrix of unsigned Stirling numbers of the first kind with the matrix of Stirling numbers of the second kind gives the Lah numbers: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L = |s| \cdot S} .

Enumeratively, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\{{\!n\! \atop \!k\!}\right\}, \left[{n \atop k}\right] , L(n,k)} 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \biggl\{{\!n\! \atop \!k\!}\biggr\} \leq \biggl[{n \atop k}\biggr] \leq L(n,k).}

Inversion relations and the Stirling transform

For any pair of sequences, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{f_n\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{g_n\}} , related by a finite sum Stirling number formula given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\} f_k, }

for all integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq 0} , we have a corresponding inversion formula for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n} given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n = \sum_{k=0}^{n} \left[\begin{matrix} n \\ k \end{matrix} \right] (-1)^{n-k} g_k. }

The lower indices could be any integer between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} .

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \widehat{G}(z) = \widehat{F}\left(e^z-1\right)}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \widehat{F}(z) = \widehat{G}\left(\log(1+z)\right). }

For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = d/dx} , the differential operators Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^nD^n} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (xD)^n} are related by the following formulas for all integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq 0} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} (xD)^n &= \sum_{k=0}^n S(n, k) x^k D^k \\ x^n D^n &= \sum_{k=0}^n s(n, k) (xD)^k = (xD)_n = xD(xD - 1)\ldots (xD - n + 1) \end{align} }

Another pair of "inversion" relations involving the Stirling numbers relate the forward differences and the ordinary Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{th}} derivatives of a function, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , which is analytic for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} by the formulas

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{k!} \frac{d^k}{dx^k} f(x) = \sum_{n=k}^{\infty} \frac{s(n, k)}{n!} \Delta^n f(x)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{k!} \Delta^k f(x) = \sum_{n=k}^{\infty} \frac{S(n, k)}{n!} \frac{d^n}{dx^n} f(x). }

Similar properties

Table of similarities

Stirling numbers of the first kind	Stirling numbers of the second kind
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n+1\atop k}\right] = n \left[{n\atop k}\right] + \left[{n\atop k-1}\right]}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n \left[{n\atop k}\right] = n!}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n \left\{ {n \atop k} \right\} = B_n} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_n} is the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} th Bell number
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n \left[{n\atop k}\right] x^k = x^{(n)}} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x^{(n)}\}_{n\in\N} } are the rising factorials	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n \left\{ {n \atop k} \right\} x^k = T_n(x)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{T_n\}_{n\in\N} } are the Touchard polynomials
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n\atop 0}\right] = \delta_n,\ \left[{n\atop n-1}\right] = \binom{n}{2},\ \left[{n\atop n}\right] = 1}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n\atop 0}\right\} = \delta_n,\ \left\{{n\atop n-1}\right\} = \binom{n}{2},\ \left\{{n\atop n}\right\} = 1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n+1\atop k+1}\right] = \sum_{j=k}^n \left[{n\atop j}\right] \binom{j}{k} }	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n \binom{n}{j} \left\{{ j \atop k }\right\} }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[\begin{matrix} n+1 \\ k+1 \end{matrix} \right] = \sum_{j=k}^n \frac{n!}{j!} \left[{j \atop k} \right]}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n (k+1)^{n-j} \left\{{j \atop k}\right\} }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{ n+k+1 \atop n }\right] = \sum_{j=0}^k (n+j) \left[{n+j \atop j}\right]}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n+k+1 \atop k}\right\} = \sum_{j=0}^k j \left\{{ n+j \atop j }\right\}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n \atop l+m } \right] \binom{l+m}{l} = \sum_k \left[{k \atop l} \right] \left[{n-k \atop m } \right] \binom{n}{k} }	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n \atop l+m } \right\} \binom{l+m}{l} = \sum_k \left\{{k \atop l} \right\} \left\{{n-k \atop m } \right\} \binom{n}{k} }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n+k \atop n} \right] \underset{n \to \infty}{\sim} \frac{n^{2k}}{2^k k!}. }	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n+k \atop n}\right\} \underset{n \to \infty}{\sim} \frac{n^{2k}}{2^k k!}.}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=k}^\infty\left[{n\atop k}\right] \frac{x^n}{n!} = \frac{(-\log(1-x))^k}{k!}.}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=k}^\infty \left\{ {n \atop k} \right\} \frac{x^n}{n!} = \frac{(e^x-1)^k}{k!}.}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{n \atop k} \right] = \sum_{0 \leq i_1 < \cdots < i_{n-k} < n} i_1 i_2 \cdots i_{n-k}.}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ {n \atop k} \right\} = \sum_{ \begin{smallmatrix} c_1 + \cdots + c_k = n-k\\ c_1, \ldots, c_k \geq 0 \end{smallmatrix} } 1^{c_1} 2^{c_2} \cdots k^{c_k} }

See the specific articles for details.

Symmetric formulae

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{ n \atop k } \right] = \sum_{j=n}^{2n-k} (-1)^{j-k} \binom{j-1}{k-1} \binom{2n-k}{j} \left\{{ j-k \atop j-n} \right\} }

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{n \atop k}\right\} = \sum_{j=n}^{2n-k} (-1)^{j-k} \binom{j-1}{k-1} \binom{2n-k}{j} \left[{j-k \atop j-n } \right] }

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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \biggl[{n \atop k}\biggr] = \biggl\{{\!-k\! \atop \!-n\!}\biggr\} \quad \text{and} \quad \biggl\{{\!n\! \atop \!k\!}\biggr\} = \biggl[{-k \atop -n}\biggr]}

when n and k are nonnegative integers. So we have the following table for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[{-n \atop -k}\right]} :

k n	−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

Donald Knuth defined the more general Stirling numbers by extending a recurrence relation to all integers. In this approach, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{n \atop k}\right]} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\{{\!n\! \atop \!k\!}\right\}} 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,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \biggl[{n \atop k}\biggr] = \biggl\{{\!-k\! \atop \!-n\!}\biggr\} \quad \text{and} \quad \biggl\{{\!n\! \atop \!k\!}\biggr\} = \biggl[{-k \atop -n}\biggr].}

On the other hand, for positive integers n and k, David Branson defined Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{-n \atop -k}\right]\!,} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\{{\!-n\! \atop \!-k\!}\right\}\!,} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{-n \atop k}\right]\!,} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\{{\!-n\! \atop \!k\!}\right\}} (but not Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{n \atop -k}\right]} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\{{\!n\! \atop \!-k\!}\right\}} ). In this approach, one has the following extension of the recurrence relation of the Stirling numbers of the first kind:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \biggl[{-n \atop k}\biggr] = \frac{(-1)^{n+1}}{n!}\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i^k} \binom ni } ,

For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{-5 \atop k}\right] = \frac1{120}\Bigl(5-\frac{10}{2^k}+\frac{10}{3^k}-\frac 5{4^k}+\frac 1{5^k}\Bigr).} This leads to the following table of values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \left[{n \atop k}\right]} for negative integral n.

k n	0	1	2	3	4
−1	1	1	1	1	1
−2	−1/2	−3/4	−7/8	−15/16	−31/32
−3	1/6	11/36	85/216	575/1296	3661/7776
−4	−1/24	−25/288	−415/3456	−5845/41472	−76111/497664
−5	1/120	137/7200	12019/432000	874853/25920000	58067611/1555200000

In this case Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \sum_{n=1}^{\infty}\left[{-n \atop -k}\right]=B_{k} } where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_{k}} is a Bell number, and so one may define the negative Bell numbers by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \sum_{n=1}^{\infty}\left[{-n \atop k}\right]=:B_{-k}} .

For example, this produces Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \sum_{n=1}^{\infty}\left[{-n \atop 1}\right]=B_{-1}=\frac 1e\sum_{j=1}^\infty\frac1{j\cdot j!}=\frac 1e\int_0^1\frac{e^t-1}{t}dt=0.4848291\dots} , generally Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle B_{-k}=\frac 1e\sum_{j=1}^\infty\frac1{j^kj!} } .

See also

• Bell polynomials
• Catalan number
• Cycles and fixed points
• Pochhammer symbol
• Polynomial sequence
• Touchard polynomials
• Stirling permutation

References

• Rosen, Kenneth H., ed. (2018), Handbook of Discrete and Combinatorial Mathematics, CRC Press, ISBN 978-1-5848-8780-5
• Mansour, Toufik; Schork, Mathias (2015), Commutation Relations, Normal Ordering, and Stirling Numbers, CRC Press, ISBN 978-1-4665-7989-7

Further reading

• Adamchik, Victor (1997). "On Stirling Numbers and Euler Sums" (PDF). Journal of Computational and Applied Mathematics. 79: 119–130. doi:10.1016/s0377-0427(96)00167-7. Archived (PDF) from the original on 2004-12-14.
• Benjamin, Arthur T.; Preston, Gregory O.; Quinn, Jennifer J. (2002). "A Stirling Encounter with Harmonic Numbers" (PDF). Mathematics Magazine. 75 (2): 95–103. CiteSeerX 10.1.1.383.722. doi:10.2307/3219141. JSTOR 3219141. Archived (PDF) from the original on 2020-09-10.
• Boyadzhiev, Khristo N. (2012). "Close encounters with the Stirling numbers of the second kind" (PDF). Mathematics Magazine. 85 (4): 252–266. arXiv:1806.09468. doi:10.4169/math.mag.85.4.252. S2CID 115176876. Archived (PDF) from the original on 2015-09-05.
• Comtet, Louis (1970). "Valeur de s(n, k)". Analyse Combinatoire, Tome Second (in French): 51.
• Comtet, Louis (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht-Holland/Boston-U.S.A.: Reidel Publishing Company. ISBN 9789027703804.
• Hsien-Kuei Hwang (1995). "Asymptotic Expansions for the Stirling Numbers of the First Kind". Journal of Combinatorial Theory, Series A. 71 (2): 343–351. doi:10.1016/0097-3165(95)90010-1.
• Knuth, D.E. (1992), "Two notes on notation", Amer. Math. Monthly, 99 (5): 403–422, arXiv:math/9205211, doi:10.2307/2325085, JSTOR 2325085, S2CID 119584305
• Miksa, Francis L. (January 1956). "Stirling numbers of the first kind: 27 leaves reproduced from typewritten manuscript on deposit in the UMT File". Mathematical Tables and Other Aids to Computation: Reviews and Descriptions of Tables and Books. 10 (53): 37–38. JSTOR 2002617.
• Miksa, Francis L. (1972) [1964]. "Combinatorial Analysis, Table 24.4, Stirling Numbers of the Second Kind". In Abramowitz, Milton; Stegun, Irene A. (eds.). Handbook of Mathematical Functions (with Formulas, Graphs and Mathematical Tables). 55. U.S. Dept. of Commerce, National Bureau of Standards, Applied Math. p. 835.
• Mitrinović, Dragoslav S. (1959). "Sur les nombres de Stirling de première espèce et les polynômes de Stirling" (PDF). Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (in French) (23): 1–20. ISSN 0522-8441. Archived (PDF) from the original on 2009-06-17.
• O'Connor, John J.; Robertson, Edmund F. (September 1998). "James Stirling (1692–1770)".
• Sixdeniers, J. M.; Penson, K. A.; Solomon, A. I. (2001). "Extended Bell and Stirling Numbers From Hypergeometric Exponentiation" (PDF). Journal of Integer Sequences. 4: 01.1.4. arXiv:math/0106123. Bibcode:2001JIntS...4...14S.
• Spivey, Michael Z. (2007). "Combinatorial sums and finite differences". Discrete Math. 307 (24): 3130–3146. CiteSeerX 10.1.1.134.8665. doi:10.1016/j.disc.2007.03.052.
• Template:Cite OEIS
• Template:Cite OEIS