# Stirling number

In mathematics, Stirling numbers arise in a variety of analytic and combinatorics 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.

## Notation

Several different notations for the Stirling numbers are in use. Stirling numbers of the first kind are written with a small s, and those of the second kind with a large S. The Stirling numbers of the second kind are never negative, but those of the first kind can be negative; hence, there are notations for the "unsigned Stirling numbers of the first kind", which are the Stirling numbers without their signs. Common notations are:

${\displaystyle s(n,k)\,}$

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

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

for the unsigned Stirling numbers of the first kind, and

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

for the Stirling numbers of the second kind.

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 the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth. (The bracket notation conflicts with a common notation for the Gaussian coefficients.{{ safesubst:#invoke:Unsubst||date=__DATE__ |\$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}[citation needed] }}) 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 of the first kind

{{#invoke:main|main}}

The Stirling numbers of the first kind are the coefficients in the expansion

${\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}.}$
${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}$

Note that (x)0 = 1 because it is an empty product. Combinatorialists also sometimes use the notation ${\displaystyle x^{\underline {n\!}}}$ for the falling factorial, and ${\displaystyle x^{\overline {n\!}}}$ for the rising factorial.[1]

(Confusingly, the Pochhammer symbol that many use for falling factorials is used in special functions for rising factorials.)

The unsigned Stirling numbers of the first kind,

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

(with a lower-case "s"), count the number of permutations of n elements with k disjoint cycles.

A few of the Stirling numbers of the first kind are illustrated by the table below:

${\displaystyle {\begin{array}{ccccccccccc}&&&&&~~1~~&&&&&\\&&&&-1&&~~1~~&&&&\\&&&2&&-3&&~~1~~&&&\\&&-6&&11&&-6&&~~1~~&&\\&24&&-50&&35&&-10&&~~1~~&\\-120&&274&&-225&&85&&-15&&~~1~~\\\end{array}}}$

where

${\displaystyle s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)}$

## Stirling numbers of the second kind

{{#invoke:main|main}}

Stirling numbers of the second kind count the number of ways to partition a set of n elements into k nonempty subsets. They are denoted by ${\displaystyle S(n,k)}$ or ${\displaystyle \textstyle \lbrace {n \atop k}\rbrace }$.[2] The sum

${\displaystyle \sum _{k=0}^{n}S(n,k)=B_{n}}$

is the nth Bell number.

Using falling factorials, we can characterize the Stirling numbers of the second kind by the identity

${\displaystyle \sum _{k=0}^{n}S(n,k)(x)_{k}=x^{n}.}$

## Lah numbers

{{#invoke:main|main}}

The Lah numbers ${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}}$ are sometimes called Stirling numbers of the third kind. For example, see Jozsef Sándor and Borislav Crstici, Handbook of Number Theory II, Volume 2.

## Inversion relationships

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

${\displaystyle \sum _{j=0}^{n}s(n,j)S(j,k)=\delta _{nk}}$

and

${\displaystyle \sum _{j=0}^{n}S(n,j)s(j,k)=\delta _{nk},}$

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

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

A generalization of the inversion relationship gives the link with the Lah numbers ${\displaystyle L(n,k):}$

${\displaystyle (-1)^{n}L(n,k)=\sum _{z}(-1)^{z}s(n,z)S(z,k),}$

## Symmetric formulae

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

${\displaystyle 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

${\displaystyle 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).}$

## References

1. {{#invoke:citation/CS1|citation |CitationClass=book }}
2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. ISBN 0-201-14236-8, p. 244.
• M. Abramowitz and I. Stegun (Eds.). Stirling Numbers of the First Kind., §24.1.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 824, 1972.
• Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions (with Formulas, Graphs and Mathematical Tables), U.S. Dept. of Commerce, National Bureau of Standards, Applied Math. Series 55, 1964, 1046 pages (9th Printing: November 1970) - Combinatorial Analysis, Table 24.4, Stirling Numbers of the Second Kind (author: Francis L. Miksa), p. 835.
• Victor Adamchik, "On Stirling Numbers and Euler Sums", Journal of Computational and Applied Mathematics 79 (1997) pp. 119–130.
• Arthur T. Benjamin, Gregory O. Preston, Jennifer J. Quinn, A Stirling Encounter with Harmonic Numbers, (2002) Mathematics Magazine, 75 (2) pp 95–103.
• Khristo N. Boyadzhiev, Close encounters with the Stirling numbers of the second kind (2012) Mathematics Magazine, 85 (4) pp 252–266.
• Louis Comtet, Valeur de s(nk), Analyse combinatoire, Tome second (page 51), Presses universitaires de France, 1970.
• Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, Dordrecht-Holland/Boston-U.S.A., 1974.
• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

|CitationClass=journal }}.