Discrete Mathematics > Combinatorics > Permutations >
MathWorld Contributors > Dickau >
MathWorld Contributors > Diller >
Interactive Entries > Interactive Demonstrations >

Stirling Number of the First Kind

DOWNLOAD Mathematica Notebook

The signed Stirling numbers of the first kind are variously denoted s(n,m) (Riordan 1980, Roman 1984), S_n^((m)) (Fort 1948, Abramowitz and Stegun 1972), S_n^m (Jordan 1950). Abramowitz and Stegun (1972, p. 822) summarize the various notational conventions, which can be a bit confusing (especially since an unsigned version S_1(n,m)=|s(n,m)| is also in common use). The signed Stirling number of the first kind s(n,m) is are returned by StirlingS1[n, m] in the Wolfram Language, where they are denoted S_n^((m)).

The signed Stirling numbers of the first kind s(n,m) are defined such that the number of permutations of n elements which contain exactly m permutation cycles is the nonnegative number

|s(n,m)|=(-1)^(n-m)s(n,m).
(1)

This means that s(n,m)=0 for m>n and s(n,n)=1. A related set of numbers is known as the associated Stirling numbers of the first kind. Both these and the usual Stirling numbers of the first kind are special cases of a general function d_r(n,k) which is related to the number of cycles in a permutation.

The triangle of signed Stirling numbers of the first kind is

1 -1 1 2 -3 1 -6 11 -6 1 24 -50 35 -10 1
(2)

(OEIS A008275). Special values include

s(n,0)=delta_(n0)
(3)
s(n,1)=(-1)^(n-1)(n-1)!
(4)
s(n,2)=(-1)^n(n-1)!H_(n-1)
(5)
s(n,3)=1/2(-1)^(n-1)(n-1)![H_(n-1)^2-H_(n-1)^((2))]
(6)
s(n,n-1)=-(n; 2),
(7)

where delta_(mn) is the Kronecker delta, H_n is a harmonic number, H_n^((r)) is a harmonic number of order r, and (n; k) is a binomial coefficient.

The generating function for the Stirling numbers of the first kind is

sum_(k=0)^(n)s(n,k)x^k=(x)_n
(8)
=(1+x-n)^((n))
(9)
=n!(x; n)
(10)
=(-1)^nn!(n-x-1; n),
(11)

where (x)_n is a falling factorial and x^((n)) is the rising factorial,

sum_(k=m)^infty(s(k,m))/(k!)x^k=([ln(x+1)]^m)/(m!)
(12)

for x<1 (Abramowitz and Stegun 1972, p. 824) and

sum_(k=1)^(n+1)(-1)^(n+1-k)s(n+1,k)x^(n+1-k)=product_(k=1)^(n)(1+kx)
(13)
=x^n(1+1/x)_n.
(14)

The Stirling numbers of the first kind satisfy the recurrence relation

s(n+1,m)=s(n,m-1)-ns(n,m)
(15)

for 1<=m<=n and the sum identities

s(n,m)=sum_(k=m)^nn^(k-m)s(n+1,k+1)
(16)

for m>=1 and

(m; r)s(n,m)=sum_(k=m-r)^(n-r)(n; k)s(n-k,r)s(k,m-r)
(17)

for 0<=r<=m, where (n; k) is a binomial coefficient.

The Stirling numbers of the first kind s(n,m) are connected with the Stirling numbers of the second kind S(n,m). For example, the matrices (s)_(i,j) and (S)_(i,j) are inverses of each other, where (A)_(ij) denotes the matrix with (i,j)th entry aAi,j) for i,j=1, ..., n (G. Helms, pers. comm., Apr. 28, 2006).

Other formulas include

s(n,i)=sum_(k=i)^(n)sum_(j=0)^(k)s(n,k)s(k,j)S(j,i)
(18)
S(n,i)=sum_(k=i)^(n)sum_(j=0)^(k)S(n,k)S(k,j)s(j,i)
(19)

(Roman 1984, p. 67), as well as

S(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)s(k-m+n,k)
(20)
s(n,m)=sum_(k=0)^(n-m)(-1)^k(k+n-1; k+n-m)(2n-m; n-k-m)S(k-m+n,k)
(21)
sum_(l=0)^(max(k,j)+1)s(l,j)S(k,l)=delta_(jk)
(22)
sum_(l=0)^(max(k,j)+1)s(k,l)S(l,j)=delta_(jk).
(23)
StirlingNumberFirstKind

A nonnegative (unsigned) version of the Stirling numbers gives the number of permutations of n objects having m permutation cycles (with cycles in opposite directions counted as distinct) and is obtained by taking the absolute value of the signed version. The nonnegative Stirling numbers of the first kind are variously denoted

S_1(n,m)=[n; m]=|s(n,m)|
(24)

(Graham et al. 1994). Diagrams illustrating S_1(5,1)=24, S_1(5,3)=35, S_1(5,4)=10, and S_1(5,5)=1 (Dickau) are shown above.

The unsigned Stirling numbers of the first kind satisfy

S_1(n+1,k)=nS_1(n,k)+S_1(n,k-1),
(25)

and can be generalized to noninteger arguments (a sort of "Stirling polynomial") using the identity

(Gamma(j+h))/(j^hGamma(j))=sum_(k=0)^(h)(S_1(h,h-k))/(j^k)
(26)
=1+((h-1)h)/(2j)+((h-2)(3h-1)(h-1)h)/(24j^2)+((h-3)(h-2)(h-1)^2h^2)/(48j^3)+...,
(27)

which is a generalization of an asymptotic series for a ratio of gamma functions Gamma(j+1/2)/Gamma(j) (Gosper).

Wolfram Web Resources

Mathematica »

The #1 tool for creating Demonstrations and anything technical.

 Wolfram|Alpha »

Explore anything with the first computational knowledge engine.

 Wolfram Demonstrations Project »

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.
Computerbasedmath.org »

Join the initiative for modernizing math education.

 Online Integral Calculator »

Solve integrals with Wolfram|Alpha.

 Step-by-step Solutions »

Walk through homework problems step-by-step from beginning to end. Hints help you try the next step on your own.
Wolfram Problem Generator »

Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.

 Wolfram Education Portal »

Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.

 Wolfram Language »

Knowledge-based programming for everyone.