Stirling number
95465
223020175
2008-07-02T05:46:11Z
Maxal
237258
/* References */
In [[mathematics]], '''Stirling numbers''' arise in a variety of [[combinatorics]] problems. They are named after [[James Stirling (mathematician)|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'' ([[Abramowitz and Stegun]] use an uppercase S and a [[blackletter]] S respectively).
:<math>s(n,k)</math> (signed);
:<math>c(n,k)=\left[{n \atop k}\right]=|s(n,k)|</math> (unsigned).
:<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>c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k} s(n,k)</math>
(with a lower-case "''s''") count the number of [[permutation]]s of ''n'' elements with ''k'' disjoint [[cyclic permutation|cycle]]s.
'''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]] ''S''(''n'', ''k'') (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 ''n''th [[Bell numbers|Bell number]]. If we let
:<math>(x)_n=x(x-1)(x-2)\cdots(x-n+1)</math>
(in particular, (''x'')<sub>0</sub> = 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 function]]s 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\}} (-1)^{n-k} \left[{n\atop j}\right] \left\{{k\atop n}\right\} = \delta_{jk}</math>
and
:<math>\sum_{n=0}^{\max\{j,k\}} (-1)^{n-k} \left\{{n\atop j}\right\} \left[{k\atop n}\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)=(-1)^{n-k} \left[{n\atop k}\right]</math>
Then, the [[matrix inverse|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\{{n\atop k}\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[{n\atop k}\right] = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left\{{n-k+j\atop j}\right\}</math>
and
:<math>\left\{{n\atop k}\right\} = \sum_{j=0}^{n-k} (-1)^{n-k+j} {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left[{n-k+j\atop j}\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.
* [[Donald Knuth|D.E. Knuth]], [http://www-cs-faculty.stanford.edu/~knuth/papers/tnn.tex.gz ''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, [http://members.lycos.co.uk/sobalian/index.html ''Sobalian Coefficients => ... s(n,k) as an explicit formula of first echelon ...''].
* {{planetmath reference |id=2809|title=Stirling numbers of the first kind, s(n,k)}}.
* {{planetmath reference |id=2805|title=Stirling numbers of the second kind, S(n,k)}}.
* [[Neil J. A. Sloane]], [http://www.research.att.com/~njas/sequences/index.html ''The On-Line Encyclopedia of Integer Sequences''], s(n,k): A008275 & A008276, S(n,k): A008277 & A008278.
* Francis L. Miksa (1901-1975), [http://links.jstor.org/sici?sici=0891-6837%28195601%2910%3A53%3C35%3ARADOTA%3E2.0.CO%3B2-X ''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ć, [http://pefmath2.etf.bg.ac.yu/files/23/23.pdf ''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, "[http://www-2.cs.cmu.edu/~adamchik/articles/stirling.pdf 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, ''[http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf A Stirling Encounter with Harmonic Numbers]'', (2002) Mathematics Magazine, '''75''' (2) pp 95-103.
* J. M. Sixdeniers, K. A. Penson, A. I. Solomon, ''[http://www.cs.uwaterloo.ca/journals/JIS/VOL4/SIXDENIERS/bell.pdf Extended Bell and Stirling Numbers From Hypergeometric Exponentiation]'' (2001), Journal of Integer Sequences, '''4''', Article 01.1.4.
* {{cite journal| author=Hsien-Kuei Hwang |title=Asymptotic Expansions for the Stirling Numbers of the First Kind |journal=Journal of Combinatorial Theory, Series A |volume=71 |issue=2 |pages=343-351 |year=1995 |url=http://citeseer.ist.psu.edu/577040.html |doi=10.1016/0097-3165(95)90010-1}}
* John J. O'Connor, Edmund F. Robertson, [http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Stirling.html ''James Stirling (1692-1770)''], (September 1998).
[[Category:Permutations]]
[[Category:Q-analogs]]
[[Category:Factorial and binomial topics]]
[[Category:Integer sequences]]
[[de:Stirling-Zahl]]
[[fr:Nombre de Stirling]]
[[it:Numeri di Stirling]]
[[ja:スターリング数]]
[[pl:Liczby Stirlinga]]
[[sr:Стирлингов број]]
[[sv:Stirlingtal]]
[[ta:ஸ்டர்லிங் எண்கள்]]
[[zh:斯特灵数]]