Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.8 Set Partitions: Stirling Numbers

Contents

§26.8(i) Definitions

s(n,k) denotes the Stirling number of the first kind: (-1)n-k times the number of permutations of {1,2,,n} with exactly k cycles. See Table 26.8.1.

26.8.1 s(n,n) =1,
n0,
26.8.2 s(1,k) =δ1,k,
26.8.3 (-1)n-ks(n,k)=1b1<<bn-kn-1b1b2bn-k,
n>k1.

S(n,k) denotes the Stirling number of the second kind: the number of partitions of {1,2,,n} into exactly k nonempty subsets. See Table 26.8.2.

26.8.4 S(n,n)=1,
n0,
26.8.5 S(n,k)=1c12c2kck,

where the summation is over all nonnegative integers c1,c2,,ck such that c1+c2++ck=n-k.

26.8.6 S(n,k)=1k!j=0k(-1)k-j(kj)jn.
Table 26.8.1: Stirling numbers of the first kind s(n,k).
n k
0 1 2 3 4 5 6 7 8 9 10
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 -1 09584 1 18124 -67284 22449 -4536 546 -36 1
10 0 -3 62880 10 26576 -11 72700 7 23680 -2 69325 63273 -9450 870 -45 1
Table 26.8.2: Stirling numbers of the second kind S(n,k).
n k
0 1 2 3 4 5 6 7 8 9 10
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1

§26.8(ii) Generating Functions

26.8.7 k=0ns(n,k)xk=(x-n+1)n,

where (x)n is the Pochhammer symbol: x(x+1)(x+n-1).

26.8.10 k=1nS(n,k)(x-k+1)k=xn,
26.8.11 n=0S(n,k)xn=xk(1-x)(1-2x)(1-kx),
|x|<1/k,

§26.8(iii) Special Values

For n1,

26.8.14 s(n,0) =0,
s(n,1) =(-1)n-1(n-1)!,
26.8.15 s(n,2)=(-1)n(n-1)!(1+12++1n-1),
26.8.17 S(n,0) =0,
S(n,1) =1,
S(n,2) =2n-1-1.

§26.8(iv) Recurrence Relations

26.8.18 s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k),
26.8.19 (kh)s(n,k)=j=k-hn-h(nj)s(n-j,h)s(j,k-h),
nkh,
26.8.22 S(n,k)=kS(n-1,k)+S(n-1,k-1),
26.8.23 (kh)S(n,k)=j=k-hn-h(nj)S(n-j,h)S(j,k-h),
nkh,

§26.8(v) Identities

26.8.28 k=1ns(n,k)=0,
n>1,
26.8.29 k=1n(-1)n-ks(n,k)=n!,
26.8.30 j=kns(n+1,j+1)nj-k=s(n,k).
26.8.31 1k!kxkf(x)=n=ks(n,k)n!Δnf(x),

when f(x) is analytic for all x, and the series converges, where

26.8.32 Δf(x)=f(x+1)-f(x);

compare §3.6(i).

26.8.33 S(n,n-k)=j=0k(-1)j(n-1+jk+j)(n+kk-j)s(k+j,j),
26.8.34 j=0njkxj=j=0kS(k,j)xjjxj(1-xn+11-x),
26.8.35 j=0njk=j=0kj!S(k,j)(n+1j+1),
26.8.36 k=0n(-1)n-kk!S(n,k)=1.
26.8.37 1k!Δkf(x)=n=kS(n,k)n!nxnf(x),

when f(x) is analytic for all x, and the series converges.

Let A and B be the n×n matrices with (j,k)th elements s(j,k), and S(j,k), respectively. Then

26.8.38 A-1=B.
26.8.39 j=kns(j,k)S(n,j)=j=kns(n,j)S(j,k)=δn,k.

§26.8(vi) Relations to Bernoulli Numbers

See §24.15(iii).

§26.8(vii) Asymptotic Approximations

26.8.40 s(n+1,k+1)(-1)n-kn!k!(γ+lnn)k,
n,

uniformly for k=o(lnn), where γ is Euler’s constant (§5.2(ii)).

26.8.41 s(n+k,k)(-1)n2nn!k2n,
k,

n fixed.

For asymptotic approximations for s(n+1,k+1) and S(n,k) that apply uniformly for 1kn as n see Temme (1993).

For other asymptotic approximations and also expansions see Moser and Wyman (1958a) for Stirling numbers of the first kind, and Moser and Wyman (1958b), Bleick and Wang (1974) for Stirling numbers of the second kind.

For asymptotic estimates for generalized Stirling numbers see Chelluri et al. (2000).