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''' \ ''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
| −1
| 1
|-
|'''3'''
| 0
| 2
| −3
| 1
|-
|'''4'''
| 0
| −6
| 11
| −6
| 1
|-
|'''5'''
| 0
| 24
| −50
| 35
| −10
| 1
|-
|'''6'''
| 0
| −120
| 274
| −225
| 85
| −15
| 1
|-
|'''7'''
| 0
| 720
| −1764
| 1624
| −735
| 175
| −21
| 1
|-
|'''8'''
| 0
| −5040
| 13068
| −13132
| 6769
| −1960
| 322
| −28
| 1
|-
|'''9'''
| 0
| 40320
| −109584
| 118124
| −67284
| 22449
| −4536
| 546
| −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'' − 3 cycles?
There are three possibilities:
* ''n'' − 6 fixed points and three two-cycles
* ''n'' − 5 fixed points, a three-cycle and a two-cycle, and
* ''n'' − 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''| < 1 (the singularity nearest to ''z'' = 0 of log(1 + ''z'') is at ''z'' = −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'', 0) = 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'', ''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, 2) = 11, corresponds to the fact that the [[symmetric group]] on 4 objects has 3 permutations of the form
:<math> (\bullet\bullet)(\bullet\bullet)</math> — 2 orbits of size 2 each
and 8 permutations of the form
:<math> (\bullet\bullet\bullet)</math> — 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'' + 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'', ''k'' − 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>, ..., ''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'' + 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'' ''s''(''n'', ''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:ஸ்டர்லிங் சுழல் எண்]]