Stirling number

Template:Short description Template:Use American English 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).Template:Sfn They were rediscovered and given a combinatorial meaning by Masanobu Saka in his 1782 Sanpō-Gakkai (The Sea of Learning on Mathematics).Template:Sfn<ref>Template:Cite book</ref>

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

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Several different notations for Stirling numbers are in use. Ordinary (signed) Stirling numbers of the first kind are commonly denoted:

<math> s(n,k)\,.</math>

Unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles, are denoted:

<math> \biggl[{n \atop k}\biggr] =c(n,k)=|s(n,k)|=(-1)^{n-k} s(n,k)\,</math>

Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets:<ref>Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. Template:Isbn, p. 244.</ref>

<math> \biggl\{{\!n\! \atop \!k\!}\biggr\} = S(n,k) = S_n^{(k)} \,</math>

Abramowitz and Stegun use an uppercase <math>S</math> and a blackletter <math>\mathfrak S</math>, 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.<ref>Template:Cite journal</ref> 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 <math>s_1(n,k)</math> and <math>s_2(n,k)</math>.

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.

That is, the falling factorial, defined as <math>\ (x)_{n} = x(x-1)\ \cdots(x-n+1)\ ,</math> is a polynomial in Template:Mvar of degree Template:Mvar whose expansion is

<math>(x)_{n}\ =\ \sum_{k=0}^n\ s(n,k)\ x^k\ </math>

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

Note that <math>\ (x)_0 \equiv 1\ ,</math> by convention, because it is an empty product. The notations <math style="vertical-align:baseline;">\ x^{\underline{n}}\ </math> for the falling factorial and <math style="vertical-align:baseline;">\ x^{\overline{n}}\ </math> for the rising factorial are also often used.<ref>Template:Cite book</ref> (Confusingly, the Pochhammer symbol that many use for falling factorials is used in special functions for rising factorials.)

Similarly, the rising factorial, defined as <math>\ x^{(n)}\ =\ x(x+1)\ \cdots(x+n-1)\ ,</math> is a polynomial in Template:Mvar of degree Template:Mvar whose expansion is

<math> 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\ ,</math>

with unsigned Stirling numbers of the first kind as coefficients. One of these expansions can be derived from the other by observing that <math>\ x^{(n)} = (-1)^n (-x)_{n} ~.</math>

Stirling numbers of the second kind express the reverse relations:

<math>\ x^n\ =\ \sum_{k=0}^n\ S(n,k)\ (x)_k\ </math>

and

<math>\ x^n\ =\ \sum_{k=0}^n\ (-1)^{n-k}\ S(n,k)\ x^{(k)} ~.</math>

As change of basis coefficients

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

<math>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</math>

is a basis. That is, every polynomial in x can be written as a sum <math>a_0 x^{(0)} + a_1 x^{(1)} + \dots + a_n x^{(n)}</math> for some unique coefficients <math>a_i</math> (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 <math>x^n</math> with falling and rising factorials as above.

Falling factorials define, up to scaling, the same polynomials as binomial coefficients: <math display="inline">\binom{x}{k} = (x)_k/k!</math>. The changes between the standard basis <math>\textstyle x^0, x^1, x^2, \dots</math> and the basis <math display="inline">\binom{x}{0}, \binom{x}{1}, \binom{x}{2}, \dots</math> are thus described by similar formulas:

<math>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</math>.

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 expressed as another falling factorial (for <math>k\ne-1</math>)

<math>\sum_{0\leq i < n} (i)_k = \frac{(n)_{k+1}}{k+1} </math>

This can be proved by induction.

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

<math>\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}</math>

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 <math display="inline">\sum_{i=0}^n i^k</math> 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:

<math>\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}</math>

and

<math>\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},</math>

where <math>\delta_{nk}</math> 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 <math>s_{nk}=s(n,k).\,</math> The inverse of this matrix is S, the lower triangular matrix of Stirling numbers of the second kind, whose entries are <math>S_{nk}=S(n,k).</math> Symbolically, this is written

<math>s^{-1} = S\,</math>

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

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

The Lah numbers <math>L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}</math> are sometimes called Stirling numbers of the third kind.<ref>Template:Cite book</ref> By convention, <math>L(0,0)=1</math> and <math>L(n,k)=0</math> if <math>n<k</math> or <math>k = 0 < n</math>.

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

<math>x^{(n)} = \sum_{k=0}^n L(n,k) (x)_k\quad</math> and <math>\quad(x)_n = \sum_{k=0}^n (-1)^{n-k} L(n,k)x^{(k)}.</math>

As above, this means they express the change of basis between the bases <math>(x)_0,(x)_1,(x)_2,\cdots</math> and <math>x^{(0)},x^{(1)},x^{(2)},\cdots</math>, completing the diagram. In particular, one formula is the inverse of the other, thus:

<math>\sum_{j=k}^n (-1)^{j-k} L(n,j) L(j,k) = \delta_{n,k}.</math>

Similarly, composing the change of basis from <math>x^{(n)}</math> to <math>x^n</math> with the change of basis from <math>x^n</math> to <math>(x)_{n}</math> gives the change of basis directly from <math>x^{(n)}</math> to <math>(x)_{n}</math>:

<math> L(n,k) = \sum_{j=k}^n \biggl[{n \atop j}\biggr] \biggl\{{\!j\! \atop \!k\!}\biggr\} ,</math>

and similarly for other compositions. In terms of matrices, if <math>L</math> denotes the matrix with entries <math>L_{nk}=L(n,k)</math> and <math>L^{-}</math> denotes the matrix with entries <math>L^{-}_{nk}=(-1)^{n-k}L(n,k)</math>, then one is the inverse of the other: <math> L^{-} = L^{-1}</math>. 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: <math>L = |s| \cdot S</math>.

Enumeratively, <math display="inline">\left\{{\!n\! \atop \!k\!}\right\}, \left[{n \atop k}\right] , L(n,k)</math> 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:

<math>\biggl\{{\!n\! \atop \!k\!}\biggr\} \leq \biggl[{n \atop k}\biggr] \leq L(n,k).</math>

Inversion relations and the Stirling transform

For any pair of sequences, <math>\{f_n\}</math> and <math>\{g_n\}</math>, related by a finite sum Stirling number formula given by

<math>g_n = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\} f_k, </math>

for all integers <math>n \geq 0</math>, we have a corresponding inversion formula for <math>f_n</math> given by

<math>f_n = \sum_{k=0}^{n} \left[\begin{matrix} n \\ k \end{matrix} \right] (-1)^{n-k} g_k. </math>

The lower indices could be any integer between <math display="inline">0</math> and <math display="inline">n</math>.

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

<math>\widehat{G}(z) = \widehat{F}\left(e^z-1\right)</math>

and

<math>\widehat{F}(z) = \widehat{G}\left(\log(1+z)\right). </math>

For <math>D = d/dx</math>, the differential operators <math>x^nD^n</math> and <math>(xD)^n</math> are related by the following formulas for all integers <math>n \geq 0</math>:<ref>Concrete Mathematics exercise 13 of section 6. Note that this formula immediately implies the first positive-order Stirling number transformation given in the main article on generating function transformations.</ref>

<math>

\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} </math>

Another pair of "inversion" relations involving the Stirling numbers relate the forward differences and the ordinary <math>n^{th}</math> derivatives of a function, <math>f(x)</math>, which is analytic for all <math>x</math> by the formulas<ref>Template:Cite journal (Section 26.8)</ref>

<math>\frac{1}{k!} \frac{d^k}{dx^k} f(x) = \sum_{n=k}^{\infty} \frac{s(n, k)}{n!} \Delta^n f(x)</math>

<math>\frac{1}{k!} \Delta^k f(x) = \sum_{n=k}^{\infty} \frac{S(n, k)}{n!} \frac{d^n}{dx^n} f(x). </math>

Similar properties

Table of similarities

Stirling numbers of the first kind	Stirling numbers of the second kind
<math> \left[{n+1\atop k}\right] = n \left[{n\atop k}\right] + \left[{n\atop k-1}\right]</math>	<math>\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} </math>
<math>\sum_{k=0}^n \left[{n\atop k}\right] = n!</math>	<math>\sum_{k=0}^n \left\{ {n \atop k} \right\} = B_n</math>, where <math>B_n</math> is the <math>n</math>th Bell number
<math>\sum_{k=0}^n \left[{n\atop k}\right] x^k = x^{(n)}</math>, where <math>\{x^{(n)}\}_{n\in\N} </math> are the rising factorials	<math>\sum_{k=0}^n \left\{ {n \atop k} \right\} x^k = T_n(x)</math>, where <math>\{T_n\}_{n\in\N} </math> are the Touchard polynomials
<math> \left[{n\atop 0}\right] = \delta_n,\ \left[{n\atop n-1}\right] = \binom{n}{2},\ \left[{n\atop n}\right] = 1</math>	<math> \left\{{n\atop 0}\right\} = \delta_n,\ \left\{{n\atop n-1}\right\} = \binom{n}{2},\ \left\{{n\atop n}\right\} = 1</math>
<math>\left[{n+1\atop k+1}\right] = \sum_{j=k}^n \left[{n\atop j}\right] \binom{j}{k} </math>	<math>\left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n \binom{n}{j} \left\{{ j \atop k }\right\} </math>
<math>\left[\begin{matrix} n+1 \\ k+1 \end{matrix} \right] = \sum_{j=k}^n \frac{n!}{j!} \left[{j \atop k} \right]</math>	<math> \left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n (k+1)^{n-j} \left\{{j \atop k}\right\} </math>
<math>\left[{ n+k+1 \atop n }\right] = \sum_{j=0}^k (n+j) \left[{n+j \atop j}\right]</math>	<math>\left\{{n+k+1 \atop k}\right\} = \sum_{j=0}^k j \left\{{ n+j \atop j }\right\}</math>
<math>\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} </math>	<math>\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} </math>
<math>\left[{n+k \atop n} \right] \underset{n \to \infty}{\sim} \frac{n^{2k}}{2^k k!}. </math>	<math> \left\{{n+k \atop n}\right\} \underset{n \to \infty}{\sim} \frac{n^{2k}}{2^k k!}.</math>
<math>\sum_{n=k}^\infty\left[{n\atop k}\right] \frac{x^n}{n!} = \frac{(-\log(1-x))^k}{k!}.</math>	<math> \sum_{n=k}^\infty \left\{ {n \atop k} \right\} \frac{x^n}{n!} = \frac{(e^x-1)^k}{k!}.</math>
<math> \left[{n \atop k} \right] = \sum_{0 \leq i_1 < \ldots < i_{n-k} < n} i_1 i_2 \cdots i_{n-k}.</math>	<math> \left\{ {n \atop k} \right\} = \sum_{ \begin{array}{c} c_1 + \ldots + c_k = n-k\\ c_1, \ldots,\ c_k\ \geq\ 0 \end{array} } 1^{c_1} 2^{c_2} \cdots k^{c_k} </math>

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.<ref>Template:Citation</ref>

<math> \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\} </math>

and

<math>

\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] </math>

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.<ref name="Loeb">Template:Cite journal</ref><ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref name=":1">D.E. Knuth, 1992.</ref> Regardless of the approach taken, it is worth noting that Stirling numbers of first and second kind are connected by the relations:

<math>\biggl[{n \atop k}\biggr] = \biggl\{{\!-k\! \atop \!-n\!}\biggr\} \quad \text{and} \quad

\biggl\{{\!n\! \atop \!k\!}\biggr\} = \biggl[{-k \atop -n}\biggr]</math>

when n and k are nonnegative integers. So we have the following table for <math>\left[{-n \atop -k}\right]</math>:

Template:Diagonal split header	Template:Rh | −1	Template:Rh | −2	Template:Rh | −3	Template:Rh | −4	Template:Rh | −5
Template:Rh | −1	1	1	1	1	1
Template:Rh | −2	0	1	3	7	15
Template:Rh | −3	0	0	1	6	25
Template:Rh | −4	0	0	0	1	10
Template:Rh | −5	0	0	0	0	1

Donald Knuth<ref name=":1" /> defined the more general Stirling numbers by extending a recurrence relation to all integers. In this approach, <math display=inline> \left[{n \atop k}\right]</math> and <math display=inline>\left\{{\!n\! \atop \!k\!}\right\}</math> 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,

<math>\biggl[{n \atop k}\biggr] = \biggl\{{\!-k\! \atop \!-n\!}\biggr\} \quad \text{and} \quad

\biggl\{{\!n\! \atop \!k\!}\biggr\} = \biggl[{-k \atop -n}\biggr].</math>

On the other hand, for positive integers n and k, David Branson<ref name=":0" /> defined <math display=inline> \left[{-n \atop -k}\right]\!,</math> <math display=inline>\left\{{\!-n\! \atop \!-k\!}\right\}\!,</math> <math display=inline> \left[{-n \atop k}\right]\!,</math> and <math display=inline>\left\{{\!-n\! \atop \!k\!}\right\}</math> (but not <math display=inline> \left[{n \atop -k}\right]</math> or <math display=inline>\left\{{\!n\! \atop \!-k\!}\right\}</math>). In this approach, one has the following extension of the recurrence relation of the Stirling numbers of the first kind:

<math> \biggl[{-n \atop k}\biggr]

= \frac{(-1)^{n+1}}{n!}\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i^k} \binom ni </math>,

For example, <math display=inline>\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).</math> This leads to the following table of values of <math display=inline>\left[{n \atop k}\right]</math> for negative integral n.

Template:Diagonal split header	0	1	2	3	4
−1	1	1	1	1	1
−2	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac
−3	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac
−4	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac
−5	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac	Template:Sfrac

In this case <math display=inline>\sum_{n=1}^{\infty}\left[{-n \atop -k}\right]=B_{k} </math> where <math>B_{k}</math> is a Bell number, and so one may define the negative Bell numbers by <math display=inline>\sum_{n=1}^{\infty}\left[{-n \atop k}\right]=:B_{-k}</math>.

For example, this produces <math display=inline>\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</math>, generally <math display=inline>B_{-k}=\frac 1e\sum_{j=1}^\infty\frac1{j^kj!} </math>.

See also

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

References

• Template:Citation
• Template:Citation

Further reading

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Citation
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• {{#invoke:citation/CS1|citation

|CitationClass=web }}

• Template:Cite journal
• Template:Cite journal
• Template:Cite OEIS
• Template:Cite OEIS