TOPICS

Stirling Number of the First Kind

DOWNLOAD Mathematica NotebookDownload Wolfram 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 1996).

See also

Associated Stirling Number of the First Kind, Harmonic Number, Permutation, Permutation Cycle, Stirling Number of the Second Kind, Stirling Polynomial, Stirling Transform

Related Wolfram sites

http://functions.wolfram.com/IntegerFunctions/StirlingS1/

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (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.Adamchik, V. "On Stirling Numbers and Euler Sums." J. Comput. Appl. Math. 79, 119-130, 1997.Appell, P. "Développments en série entière de (1+ax)^(1/x)." Grunert Archiv 65, 171-175, 1880.Butzer, P. L. and Hauss, M. "Stirling Functions of the First and Second Kinds; Some New Applications." Israel Mathematical Conference Proceedings: Approximation, Interpolation, and Summability, in Honor of Amnon Jakimovski on his Sixty-Fifth Birthday (Ed. S. Baron and D. Leviatan). Ramat Gan, Israel: IMCP, pp. 89-108, 1991.Carlitz, L. "On Some Polynomials of Tricomi." Boll. Un. M. Ital. 13, 58-64, 1958.Carlitz, L. "Note on Nörlund's [sic] Polynomial B_n^((z))." Proc. Amer. Math. Soc. 11, 452-455, 1960.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, 1974.Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 91-92, 1996.David, F. N.; Kendall, M. G.; and Barton, D. E. Symmetric Function and Allied Tables. Cambridge, England: Cambridge University Press, p. 226, 1966.Dickau, R. M. "Stirling Numbers of the First Kind." http://mathforum.org/advanced/robertd/stirling1.html.Fort, T. Finite Differences and Difference Equations in the Real Domain. Oxford, England: Clarendon Press, 1948.Gosper, R. W. "Funny Looking Sum." math-fun@cs.arizona.edu posting, July 24, 1996.Gould, H. W. "Stirling Number Representation Problems." Proc. Amer. Math. Soc. 11, 447-451, 1960.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Stirling Numbers." §6.1 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 257-267, 1994.Hauss, M. Verallgemeinerte Stirling, Bernoulli und Euler Zahlen, deren Anwendungen und schnell konvergente Reihen für Zeta Funktionen. Aachen, Germany: Verlag Shaker, 1995.Jordan, C. Calculus of Finite Differences, 3rd ed. New York: Chelsea, 1965.Knuth, D. E. "Two Notes on Notation." Amer. Math. Monthly 99, 403-422, 1992.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Roman, S. The Umbral Calculus. New York: Academic Press, pp. 59-63, 1984.Sloane, N. J. A. Sequences A000457/M4736, A008275, and A008306 in "The On-Line Encyclopedia of Integer Sequences."Stirling, J. Methodus differentialis, sive tractatus de summation et interpolation serierum infinitarium. London, 1730. English translation by Holliday, J. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series. 1749.Tricomi, F. G. "A Class of Non-Orthogonal Polynomials Related to those of Laguerre." J. Analyse M. 1, 209-231, 1951.Young, P. T. "Congruences for Bernoulli, Euler, and Stirling Numbers." J. Number Th. 78, 204-227, 1999.

Referenced on Wolfram|Alpha

Stirling Number of the First Kind

Cite this as:

Weisstein, Eric W. "Stirling Number of the First Kind." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html

Subject classifications