In mathematics, Stirling numbers arise in a variety of 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.
Contents |
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 (Abramowitz and Stegun use an uppercase S and a blackletter S respectively).
- <math>s(n,k)=\left[\begin{matrix} n \\ k \end{matrix}\right].</math>
- <math>S(n,k)= S_n^{(k)} =
\left\{\begin{matrix} n \\ k \end{matrix}\right\}.</math> The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation. 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
Unsigned Stirling numbers of the first kind
- <math>|s(n,k)|\,</math>
(with a lower-case "s") count the number of permutations of n elements with k disjoint cycles. Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion
- <math>(x)_{(n)} = \sum_{k=1}^n s(n,k) x^k.</math>
where <math>(x)_{(n)}</math> is the falling factorial
- <math>(x)_{(n)}=x(x-1)(x-2)\cdots(x-n+1).</math>
- See the main article Stirling numbers of the first kind for additional information.
Stirling numbers of the second kind
Stirling numbers of the second kind <math>S(n,k)</math> (with a capital "S") count the number of ways to partition a set of n elements into k nonempty subsets. The sum
- <math>B_n=\sum_{k=1}^n S(n,k)</math>
is the nth Bell number. If we let
- <math>(x)_n=x(x-1)(x-2)\cdots(x-n+1)</math>
(in particular, (x)0 = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by
- <math>\sum_{k=0}^n S(n,k)(x)_k=x^n.</math>
(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.)
- See the main article Stirling numbers of the second kind for additional information.
Inversion relationships
The Stirling numbers of the first and second kind can be considered to be inverses of one-another:
- <math>\sum_{n=0}^{\max\{j,k\}}
\left[\begin{matrix} n \\ j \end{matrix}\right] \left\{\begin{matrix} k \\ n \end{matrix}\right\} = \delta_{jk} </math> and
- <math>\sum_{n=0}^{\max\{j,k\}}
\left\{\begin{matrix} n \\ j \end{matrix}\right\} \left[\begin{matrix} k \\ n \end{matrix}\right] = \delta_{jk} </math> where <math>\delta_{jk}</math> is the Kronecker delta. These two relationships may be understood to be matrix inverses. That is, let <math>s</math> be the lower triangular matrix of Stirling numbers of first kind, so that it has matrix elements
- <math>[s]_{nk}=s(n,k)=\left[\begin{matrix} n \\ k \end{matrix}\right]</math>
Then, the inverse of this matrix is <math>S</math>, the lower triangular matrix of Stirling numbers of second kind. Symbolically, one writes
- <math>s^{-1} = S</math>
where the matrix elements of <math>S</math> are
- <math>[S]_{nk}=S(n,k)=\left\{\begin{matrix} n \\ k\end{matrix}\right\}.</math>
Note that although <math>s</math> and <math>S</math> are infinite, this works for finite matrices by only considering Stirling numbers up to some number <math>N</math>.
Symmetric formulae
Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind.
- <math>\left[\begin{matrix} n \\ k \end{matrix}\right] =
\sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left\{\begin{matrix} n-k+j \\ j \end{matrix}\right\} </math> and
- <math>\left\{\begin{matrix} n \\ k \end{matrix}\right\} =
\sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left[\begin{matrix} n-k+j \\ j \end{matrix}\right]. </math>
See also
- Bell polynomials
- Cycles and fixed points
- Lah number
- Pochhammer symbol
- Polynomial sequence
- Stirling transform
- Touchard polynomials
References
- M. Abramowitz, 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.
- D.E. Knuth, Two notes on notation (TeX source).
- Louis Comtet, "Valeur de s(n, k)", 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.
- André F. Labossière, Sobalian Coefficients => ... s(n,k) as an explicit formula of first echelon ....
- Stirling numbers of the first kind, s(n,k) on PlanetMath.
- Stirling numbers of the second kind, S(n,k) on PlanetMath.
- Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, s(n,k): A008275 & A008276, S(n,k): A008277 & A008278.
- Francis L. Miksa (1901-1975), 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, vol. 10, no. 53, January 1956, pp. 37-38 (Reviews and Descriptions of Tables and Books, 7[I]).
- Dragoslav S. Mitrinović, Sur les nombres de Stirling de première espèce et les polynômes de Stirling, AMS 11B73_05A19, Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (ISSN 0522-8441), no. 23, 1959 (5.V.1959), pp. 1-20.
- 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.
- J. M. Sixdeniers, K. A. Penson, A. I. Solomon, Extended Bell and Stirling Numbers From Hypergeometric Exponentiation (2001), Journal of Integer Sequences, 4, Article 01.1.4.
- Hsien-Kuei Hwang, Asymptotic Expansions for the Stirling Numbers of the First Kind (1994).
- John J. O'Connor, Edmund F. Robertson, James Stirling (1692-1770), (September 1998).
