Stirling numbers of the first kind 2229296 213149918 2008-05-18T00:40:17Z Michael Hardy 4626 /* Enumerative interpretation */ In [[mathematics]], '''Stirling numbers of the first kind''', together with the [[Stirling numbers of the second kind]], are one of the two types of [[Stirling number]]s. They commonly occur in the study of [[combinatorics]], where they count the number of permutations. The Stirling numbers of the first and second kind can be understood to be inverses of one-another, when taken as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind; further identities linking the two kinds, and general information, is given in the article on [[Stirling number]]s. ==Definition== === Stirling numbers of the first kind === Stirling numbers of the first kind (without the qualifying adjective ''unsigned'') are the coefficients in the expansion :<math>(x)_{(n)} = \sum_{k=0}^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> === Unsigned Stirling numbers of the first kind === The unsigned Stirling numbers of the first kind :<math>\left[{n \atop k}\right] = \left|s(n,k)\right| = (-1)^{n-k} s(n,k)\,</math> count the number of [[permutation]]s of ''n'' elements with ''k'' disjoint [[cyclic permutation|cycle]]s. Sometimes s(n,k) is defined as the unsigned Stirling numbers. ==Table of values== Below is a table of values for the Stirling numbers of the first kind, similar in form to [[Pascal's triangle]]: {| cellspacing="0" cellpadding="3" style="text-align:right;" |- | '''n'''&nbsp;\&nbsp;''k'' | width="4%" | ''0'' | width="10%" | ''1'' | width="11%" | ''2'' | width="12%" | ''3'' | width="13%" | ''4'' | width="12%" | ''5'' | width="11%" | ''6'' | width="10%" | ''7'' | width="9%" | ''8'' | width="4%" | ''9'' |- |'''0''' | 1 |- |'''1''' | 0 | 1 |- |'''2''' | 0 | &minus;1 | 1 |- |'''3''' | 0 | 2 | &minus;3 | 1 |- |'''4''' | 0 | &minus;6 | 11 | &minus;6 | 1 |- |'''5''' | 0 | 24 | &minus;50 | 35 | &minus;10 | 1 |- |'''6''' | 0 | &minus;120 | 274 | &minus;225 | 85 | &minus;15 | 1 |- |'''7''' | 0 | 720 | &minus;1764 | 1624 | &minus;735 | 175 | &minus;21 | 1 |- |'''8''' | 0 | &minus;5040 | 13068 | &minus;13132 | 6769 | &minus;1960 | 322 | &minus;28 | 1 |- |'''9''' | 0 | 40320 | &minus;109584 | 118124 | &minus;67284 | 22449 | &minus;4536 | 546 | &minus;36 | 1 |- |} ==Recurrence relation== The Stirling numbers of the first kind obey the [[recurrence relation]] :<math>\left[{n+1\atop k}\right] = n \left[{n\atop k}\right] + \left[{n\atop k-1}\right]</math> for <math>k > 0</math>, with the initial conditions :<math>\left[{n\atop 0}\right]=\delta_{n0} \quad \mbox{and} \quad \left[{0\atop 1}\right] = 0.</math> Where <math>\delta_{n0}</math> is the [[Kronecker delta]]. The above follows from the recurrence relation on the falling factorials: :<math>(x)_{n+1} = x(x)_n - n(x)_n.</math> ==Simple identities== Note that although :<math>\left[{0 \atop 0}\right] = 1\quad\mbox{we have}\quad\left[{n\atop 0}\right] = 0\quad \mbox{if} \quad n > 0</math> and :<math>\left[{0\atop k}\right] = 0\quad\mbox{if}\quad k > 0,\quad\mbox{or more generally,}\quad \left[{n\atop k}\right] = 0\quad\mbox{if}\quad k>n.</math> Also :<math>\left[{n \atop 1}\right] = (-1)^{n-1} (n-1)!</math> and :<math>\left[{n\atop n}\right] = 1, \quad \left[{n\atop n-1}\right] = {n \choose 2},</math> and :<math>\left[{n\atop n-2}\right] = \frac{1}{4} (3n-1) {n \choose 3}\quad\mbox{ and }\quad\left[{n\atop n-3}\right] = {n \choose 2} {n \choose 4}.</math> Similar relationships involving the Stirling numbers hold for the [[Bernoulli polynomials]]. Many relations for the Stirling numbers shadow similar relations on the [[binomial coefficient]]s. The study of these 'shadow relationships' is termed [[umbral calculus]] and culminates in the theory of [[Sheffer sequences]]. ===Combinatorial proofs=== These identities may be derived by enumerating permutations directly. For example, how many permutations on [''n''] are there that consist of ''n''&nbsp;&minus;&nbsp;3 cycles? There are three possibilities: * ''n''&nbsp;&minus;&nbsp;6 fixed points and three two-cycles * ''n''&nbsp;&minus;&nbsp;5 fixed points, a three-cycle and a two-cycle, and * ''n''&nbsp;&minus;&nbsp;5 fixed points and a four-cycle. We enumerate the three types, as follows: * choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important: ::<math>{n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6}</math> * choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles: ::<math>{n \choose 5} {5 \choose 3} \times 2</math> * choose the four elements of the four-cycle and take into account that four elements generate six four-cycles: ::<math>{n \choose 4} \times 6.</math> Sum the three contributions to obtain :<math> {n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6} + {n \choose 5} {5 \choose 3} \times 2 + {n \choose 4} \times 6 = {n \choose 2} {n \choose 4}.</math> ==Other relations== These include :<math>\left[{n\atop 2}\right] = (n-1)!\; H_{n-1},</math> where ''H''<sub>''n''</sub> is a [[harmonic number]], and :<math>\left[{n\atop 3}\right] = \frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]</math> where ''H''<sub>''n''</sub><sup>(''m'')</sup> is a [[harmonic number#Introduction|generalized harmonic number]]. A generalization of this relation to harmonic numbers is given in a later section. ==Generating function== A variety of identities may be derived by manipulating the [[generating function]]: :<math>H(z,u)= (1+z)^u = \sum_{n=0}^\infty {u \choose n} z^n = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{k=0}^n \left[{n\atop k}\right] u^k = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} \left[{n\atop k}\right] = e^{u\log(1+z)}.</math> In particular, the order of summation may be exchanged, and derivatives taken, and then ''z'' or ''u'' may be fixed. ==Finite sums== A simple sum is :<math>\sum_{k=0}^n \left[{n\atop k}\right] = n!</math> or in a more general relationship, :<math>\sum_{k=0}^a \left[{n\atop k}\right] = n! - \sum_{k=0}^n \left[{n\atop k+a+1}\right].</math> The identity :<math>\sum_{p=k}^{n} {\left[{n\atop p}\right]\binom{p}{k}} = \left[{n+1\atop k+1}\right]</math> is proved on the page about [[Stirling numbers and exponential generating functions]]. ==Infinite sums== Some infinite sums include :<math>\sum_{n=k}^\infty (-1)^{n-k} \left[{n\atop k}\right] \frac{z^n}{n!} = \frac{\left(\log (1+z)\right)^k}{k!}</math> where |''z''|&nbsp;<&nbsp;1 (the singularity nearest to ''z''&nbsp;=&nbsp;0 of log(1&nbsp;+&nbsp;''z'') is at ''z''&nbsp;=&nbsp;&minus;1.) ==Relation to harmonic numbers== Stirling numbers of the first kind can be expressed in terms of the [[harmonic number]]s :<math>H^{(m)}_n=\sum_{k=1}^n \frac{1}{k^m}</math> as follows: :<math>s(n,k)=(-1)^{k-n} \frac{\Gamma(n)}{\Gamma(k)}w(n,k-1)</math> where ''w''(''n'',&nbsp;0)&nbsp;=&nbsp;1 and :<math>w(n,k)=\sum_{m=0}^{k-1}\frac{\Gamma(1-k+m)}{\Gamma(1-k)}H_{n-1}^{(m+1)} w(n,k-1-m).</math> In the above, <math>\Gamma(x)</math> is the [[Gamma function]]. ==Enumerative interpretation== [[Image:Stirling number of the first kind s(4,2).svg|350px|thumb|s(4,2)=11]] The [[absolute value]] of the Stirling number of the first kind, ''s''(''n'',&nbsp;''k''), counts the number of [[permutation]]s of ''n'' objects with exactly ''k'' [[orbit (group theory)|orbit]]s (equivalently, with exactly ''k'' [[Cyclic permutation|cycle]]s). For example, ''s''(4,&nbsp;2)&nbsp;=&nbsp;11, corresponds to the fact that the [[symmetric group]] on 4 objects has 3 permutations of the form :<math> (\bullet\bullet)(\bullet\bullet)</math> &mdash; 2 orbits of size 2 each and 8 permutations of the form :<math> (\bullet\bullet\bullet)</math> &mdash; 1 orbit of size 3, and 1 orbit of size 1 (see the entry on [[cycle notation]] for the meaning of the above expressions.) Let us prove this. First, we can remark that the unsigned Stirling numbers of the first are characterized by the following recurrence relation: :<math> | s(n+1,k)| = | s(n,k-1)| + n| s(n,k)|,\qquad 1\leq k < n.</math> To see why the above recurrence relation matches the count of permutations with ''k'' cycles, consider forming a permutation of ''n''&nbsp;+&nbsp;1 objects from a permutation of ''n'' objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a [[singleton]] cycle, i.e. leaving the extra object alone. This accounts for the ''s''(''n'',&nbsp;''k''&nbsp;&minus;&nbsp;1) term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of ''n'' objects with ''k'' cycles, and [[vertex weighted digraph|label]] the objects ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''n''</sub>, so that the permutation is represented by :<math>\displaystyle\underbrace{(a_1 \ldots a_{j_1})(a_{j_1+1} \ldots a_{j_2})\ldots(a_{j_{k-1}+1} \ldots a_n)}_{ k\ \mathrm{cycles}}.</math> To form a new permutation of ''n''&nbsp;+&nbsp;1 objects and ''k'' cycles one must insert the new object into this array. There are, evidently ''n'' ways to perform this insertion. This explains the ''n''&nbsp;''s''(''n'',&nbsp;''k'') term of the recurrence relation. Q.E.D. ==References== <references/> * [[The Art of Computer Programming]] * [[Concrete Mathematics]] * 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. * {{planetmath reference |id=2809|title=Stirling numbers of the first kind, s(n,k)}}. *A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1<=k<=n. [http://www.research.att.com/~njas/sequences/A008275] {{planetmath|id=2809|title=Stirling numbers of the first kind}} [[Category:Permutations]] [[Category:Factorial and binomial topics]] [[Category:Triangles of numbers]] [[pl:Liczby_Stirlinga#Liczby_Stirlinga_I_rodzaju]] [[ta:ஸ்டர்லிங் சுழல் எண்]]