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'',&nbsp;''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'',&nbsp;''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:斯特灵数]]