Stirling numbers of the first kind

Introduction.

The Stirling numbers of the first kind, frequently denoted as

s(n,k)={n\\brack k},\\quad k,n\\in\\mathbb{N},\\quad 1\\leq k\\leq n,

are the integercoefficients of the falling factorial polynomials. To be more precise,the defining relation for the Stirling numbers of the first kind is:

x^{\\underline{n}}=x(x-1)(x-2)\\ldots(x-n+1)=\\sum_{k=1}^{n}s(n,k)x^{k}.

Here is the table of some initial values.

Recurrence Relation.

The evident observation that

x^{\\underline{n+1}}=xx^{\\underline{n}}-nx^{\\underline{n}}.

leads to the following equivalent characterization of the $s(n,k)$ , interms of a 2-placerecurrence formula:

s(n+1,k)=s(n,k-1)-ns(n,k),\\qquad 1\\leq k<n,

subject to thefollowing initial conditions:

s(n,0)=0,\\qquad s(1,1)=1.

Generating Function.

There is also a strong connection with the generalized binomialformula, which furnishes us with the following generating function:

(1+t)^{x}=\\sum_{n=0}^{\\infty}\\sum_{k=1}^{n}s(n,k)x^{k}\\frac{t^{n}}{n!}.

This generating function implies a number of identities.Taking the derivative of both sides with respect to $t$ and equatingpowers, leads to the recurrence relation described above.Taking the derivative of both sides with respect to $x$ gives

(k+1)s(n,k+1)=\\sum_{j=k}^{n}(-1)^{n-j}(n-j)!\\binom{n+1}{j}s(j,k)

This is because the derivative of the left side of thegenerating funcion equation with respect to $x$ is

(1+t)^{x}\\ln(1+t)=(1+t)^{x}\\sum_{k=1}^{\\infty}(-1)^{k-1}\\frac{t^{k}}{k}.

The relation

(1+t)^{x_{1}}(1+t)^{x_{2}}=(1+t)^{x_{1}+x_{2}}

yields the following family of summation identities. For any given $k_{1},k_{2},d\\geq 1$ we have

\\binom{k_{1}+k_{2}}{k_{1}}s(d+k_{1}+k_{2},k_{1}+k_{2})=\\sum_{d_{1}+d_{2}=d}%\\binom{d+k_{1}+k_{2}}{k_{1}+d_{1}}s(d_{1}+k_{1},k_{1})s(d_{2}+k_{2},k_{2}).

Enumerative interpretation.

The absolute value of the Stirling number of the first kind, $s(n,k)$ ,counts the number of permutations of $n$ objects with exactly $k$ orbits (equivalently, with exactly $k$ cycles). For example, $s(4,2)=11$ , corresponds to the fact thatthe symmetric group on 4 objects has $3$ permutations of the form

(**)(**)\\quad\\mbox{ --- 2 orbits of size 2 each},

and $8$ permutationsof the form

(***)\\quad\\mbox{ --- 1 orbit of size 3, and 1 orbit of size1},

(see the entry on cycle notation for the meaning of the aboveexpressions.)

Let us prove this. First, we can remark that the unsigned Stirlingnumbers of the first are characterized by the following recurrencerelation:

|s(n+1,k)|=|s(n,k-1)|+n|s(n,k)|,\\qquad 1\\leq k<n.

To see why the above recurrence relation matches the count ofpermutations with $k$ cycles, consider forming a permutation of $n+1$ objects from a permutation of $n$ objects by adding a distinguishedobject. There are exactly two ways in which this can be accomplished.We could do this by forming a singleton cycle, i.e. leaving the extraobject alone. This accounts for the $s(n,k-1)$ term in the recurrenceformula. We could also insert the new object into one of the existingcycles. Consider an arbitrary permutation of $n$ object with $k$ cycles, and label the objects $a_{1},\\ldots,a_{n}$ , so that thepermutation is represented by

\\underbrace{(a_{1}\\ldots a_{j_{1}})(a_{j_{1}+1}\\ldots a_{j_{2}})\\ldots(a_{j_{k%-1}+1}\\ldots a_{n})}_{\\displaystyle k\\mbox{cycles}}.

To form a new permutation of $n+1$ objects and $k$ cycles one mustinsert the new object into this array. There are, evidently $n$ waysto perform this insertion. This explains the $n\\,s(n,k)$ term of therecurrence relation. Q.E.D.