User:Tokenzero/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:

$\left[{n \atop k}\right]=c(n,k)=|s(n,k)|\,$

for unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles,

$s(n,k)=(-1)^{n-k}\left[{n \atop k}\right]\,$

for ordinary (signed) Stirling numbers of the first kind, and

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=S(n,k)=S_{n}^{(k)}\,$

for Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets.

For example, the sum $\sum _{k=0}^{n}\left[{n \atop k}\right]=n!$ is the number of all permutations, while the sum $\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=B_{n}$ is the nth Bell number.

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.

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)₀ = 1 because it is an empty product. Combinatorialists also sometimes use the notation $x^{\underline {n}}$ for the falling factorial, and $x^{\overline {n}}$ for the rising factorial. (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}\left[{n \atop k}\right]x^{k}$

with unsigned Stirling numbers of the first kind as coefficients.

Stirling numbers of the second kind express reverse relations:

$x^{n}=\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}(x)_{k}$

and

$x^{n}=\sum _{k=0}^{n}(-1)^{n-k}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}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

$x^{0},x^{1},x^{2},x^{3},\cdots \quad (x)_{0},(x)_{1},(x)_{2},\cdots \quad x^{(0)},x^{(1)},x^{(2)},\cdots$

is a basis. That is, every polynomial in x can be written as a sum $a_{0}x^{(0)}+a_{1}x^{(1)}+\dots +a_{n}x^{(n)}$ for some unique coefficients $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:

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 $x^{n}$ with falling and rising factorials as above.

As inverse matrices

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

$\sum _{j\geq 0}s(n,j)S(j,k)=\sum _{j\geq 0}(-1)^{n-j}{\begin{bmatrix}n\\j\end{bmatrix}}{\begin{Bmatrix}j\\k\end{Bmatrix}}=\delta _{nk}$

and

$\sum _{j\geq 0}S(n,j)s(j,k)=\sum _{j\geq 0}(-1)^{j-k}{\begin{Bmatrix}n\\j\end{Bmatrix}}{\begin{bmatrix}j\\k\end{bmatrix}}=\delta _{nk},$

where $\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 $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 $S_{nk}=S(n,k).$ Symbolically, this is written

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

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)

$\sum _{0\leq i<n}(i)_{k}={\frac {(n)_{k+1}}{k+1}}$

This is analogous to the integral $\textstyle \int _{0}^{n}x^{k}={\frac {n^{k+1}}{k+1}}$, though the sum should be over integers i strictly less than n.

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

${\begin{aligned}&\sum _{i=0}^{n}i^{4}=\sum _{i=0}^{n}\sum _{k=0}^{4}{\begin{Bmatrix}4\\k\end{Bmatrix}}(i)_{4}=\sum _{k=0}^{4}{\begin{Bmatrix}4\\k\end{Bmatrix}}{\frac {(n+1)_{k+1}}{k+1}}=\\&={\frac {\{{\begin{smallmatrix}4\\1\end{smallmatrix}}\}}{2}}(n+1)_{2}+{\frac {\{{\begin{smallmatrix}4\\2\end{smallmatrix}}\}}{3}}(n+1)_{3}+{\frac {\{{\begin{smallmatrix}4\\3\end{smallmatrix}}\}}{4}}(n+1)_{4}+{\frac {\{{\begin{smallmatrix}4\\4\end{smallmatrix}}\}}{5}}(n+1)_{5}=\\&={\frac {1}{2}}(n+1)_{2}+{\frac {7}{3}}(n+1)_{3}+{\frac {6}{4}}(n+1)_{4}+{\frac {1}{5}}(n+1)_{5}\end{aligned}}$

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 $\sum _{i=0}^{n}i^{k}$ in the standard basis is given by Faulhaber's formula, which in general is more complex.

Lah numbers

Main article: Lah numbers

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

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

$x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}\quad$ and $\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 $(x)_{0},(x)_{1},(x)_{2},\cdots$ and $x^{(0)},x^{(1)},x^{(2)},\cdots$, completing the diagram. In particular, one formula is the inverse of the other, thus:

$\sum _{j}L(n,j)\cdot (-1)^{j-k}L(j,k)=\delta _{nk}.$

Similarly, composing for example the change of basis from $x^{(n)}$ to $x^{n}$ with the change of basis from $x^{n}$ to $(x)_{n}$ gives the change of basis directly from $x^{(n)}$ to $(x)_{n}$:

$L(n,k)=\sum _{j}{\begin{bmatrix}n\\j\end{bmatrix}}{\begin{Bmatrix}j\\k\end{Bmatrix}},$

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

The numbers $\textstyle {\begin{Bmatrix}n\\k\end{Bmatrix}},{\begin{bmatrix}n\\k\end{bmatrix}},L(n,k)$ can be defined as the number of partitions of n elements into k non-empty subsets, each of which is unordered, cyclically ordered, or linearly ordered, respectively. In particular, this implies the following inequalities:

${\begin{Bmatrix}n\\k\end{Bmatrix}}\leq {\begin{bmatrix}n\\k\end{bmatrix}}\leq L(n,k).$

Symmetric formulae

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

$s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)$

and

$S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).$

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:

$\left[{n \atop k}\right]=\left\{{\begin{matrix}-k\\-n\end{matrix}}\right\}\,\qquad {\text{and}}\qquad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left[{-k \atop -n}\right]$

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

n \ k	-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, $\left[{n \atop k}\right]$ and $\left\{{\begin{matrix}n\\k\end{matrix}}\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,

$\left[{n \atop k}\right]=\left\{{\begin{matrix}-k\\-n\end{matrix}}\right\}\,\qquad {\text{and}}\qquad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left[{-k \atop -n}\right]$.

On the other hand, for positive integers n and k, David Branson defined $\left[{-n \atop -k}\right]$, $\left\{{\begin{matrix}-n\\-k\end{matrix}}\right\}$, $\left[{{-n} \atop k}\right]$, and $\left\{{\begin{matrix}-n\\k\end{matrix}}\right\}$ (but not $\left[{n \atop -k}\right]$ or $\left\{{\begin{matrix}n\\-k\end{matrix}}\right\}$). In this approach, from

$\left[{-n \atop k}\right]={\frac {(-1)^{n+1}}{n!}}\sum _{i=1}^{n}(-1)^{i+1}{\frac {n \choose i}{i^{k}}}$,

which is a generalizarion of the Recurrence relation of the Stirling numbers of the first kind, e.g. $\left[{-5 \atop k}\right]=(5-10/2^{k}+10/3^{k}-5/4^{k}+1/5^{k})/120$,

we have following table for $\left[{-n \atop k}\right]$:

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

Note that: $\sum _{n=-1}^{-\infty }\left[{-n \atop k}\right]=B_{-k}\qquad {\text{and}}\qquad \sum _{n=-1}^{-\infty }\left[{-n \atop -k}\right]=B_{k}$

where $B_{k}$ is the Bell number of $k$, e.g. $\sum _{n=-1}^{-\infty }\left[{-n \atop 2}\right]=B_{-2}=0.421773\ldots$

See also

• Bell polynomials
• Cycles and fixed points
• Lah number
• Pochhammer symbol
• Polynomial sequence
• Stirling transform
• Touchard polynomials

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.
• Benjamin, Arthur T.; Preston, Gregory O.; Quinn, Jennifer J. (2002). "A Stirling Encounter with Harmonic Numbers" (PDF). Mathematics Magazine. 75 (2): 95–103. doi:10.2307/3219141.
• Boyadzhiev, Khristo N. (2012). "Close encounters with the Stirling numbers of the second kind" (PDF). Mathematics Magazine. 85 (4): 252–266. doi:10.4169/math.mag.85.4.252.
• Comtet, Louis (1970). "Valeur de s(n, k)". Analyse combinatoire, Tome second (in French). Presses universitaires de France: 51.
• Comtet, Louis (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht-Holland/Boston-U.S.A.: Reidel Publishing Company.
• 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. "Two notes on notation" (TeX source).
• 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.
• 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.
• 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.
• Spivey, Michael Z. (2007). "Combinatorial sums and finite differences". Discrete Math. Vol. 307, no. 24. pp. 3130–3146. doi:10.1016/j.disc.2007.03.052.
• Sloane, N. J. A. (ed.). "Sequence A008275 (Stirling numbers of first kind)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
• Sloane, N. J. A. (ed.). "Sequence A008277 (Stirling numbers of 2nd kind)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
• "Stirling numbers of the first kind, s(n,k)". PlanetMath.
• "Stirling numbers of the second kind, S(n,k)". PlanetMath.