Stirling, bell, bernoulli, euler and eulerian numbers
- PDF / 786,447 Bytes
- 159 Pages / 595 x 842 pts (A4) Page_size
- 89 Downloads / 314 Views
STIRLING, BELL, BERNOULLI, EULER AND EULERIAN NUMBERS
5.1
Introduction
This Chapter is divided into two major parts: Stirling and Bell numbers, and Bernoulli, Euler and Eulerian numbers. These classical topics occur in practically every field of mathematics, in particular in combinatorial theory, finite difference calculus, numerical analysis, number theory, and probability theory. Our aim is to study the many aspects of these numbers, and to point out important connections or applications in number theory and related fields. In fact this Chapter underlines the many connections and aspects of certain parts of Discrete mathematics to almost the entire mathematics.
5.2 1
Stirling and Bell numbers Stirling numbers of both kinds, Lah numbers
Let S(n, k) denote the number of partitions of a set with n elements into k nonempty blocks. Then S(n, k) > 0 for 1 ≤ k ≤ n, and S(n, k) = 0 for 1 ≤ n < k. Put S(0, 0) = 1 and S(0, k) = 0 for k ≥ 1, S(n, 0) = 0 for n ≥ 1. These numbers were introduced by J. Stirling in his book ”Methodus Differentialis” [424] from 1730 (see also O. Schl¨omilch [394], J. F. Steffensen [423], 459
CHAPTER 5
N. Nielsen [333], G. Boole [56], Ch. Jordan [237] for early references, and various other notations), and are called now as the Stirling numbers of the second kind. These numbers are treated also e.g. in J. Riordan [365], [367], L. Comtet [116], P. A. Mac Mahon [295], N. E. N¨orlund [338], L. M. Milne-Thomson [310], M. Aigner [15], P. J. Davis [131], M. Abramovicz and I. A. Stegun [1], A. O. Gelfond [180], F. W. J. Olver [343], I. Tomescu [448], etc. See also D. S. Mitrinovi´c and R. S. Mitrinovi´c [311], where various tables of Stirling numbers can be found, too. The Stirling numbers of the second kind S(n, k) satisfy the recurrence relation S(n, k) = S(n − 1, k − 1) + k S(n − 1, k)
(n, k ≥ 1)
(1)
and, if we denote by (x)n = x(x − 1) . . . (x − n + 1) the falling factorial power, then n xn = S(n, k) · (x)k (2) k=0
where (x)0 = 1 by definition. This gives a ”horizontal” generating function of S(n, k). The ”vertical” generating function is given by
S(n, k)
n≥0
tn 1 = (et − 1)k n! k!
(k ≥ 0)
(3)
(Here one can take n ≥ k in place of n ≥ 0, since S(n, k) = 0 for n < k). Similarly, the ”rational” generating function is 1 S(n, k)u n−k = (k ≥ 1) (4) (1 − u)(1 − 2u) . . . (1 − ku) n≥0 In fact, S(n, k) can be explicitly calculated with the aid of binomial coefficients: k 1 i k (k − i)n (−1) (5) S(n, k) = k! i=0 i and have the following vertical, resp. horizontal recurrences (see e.g. [116]) n−1 n−1 S(l, k − 1), S(n, k) = l l=k−1 S(n, k) =
n
S(l − 1, k − 1)k n−l ,
(6) (7)
l=k
S(n, k) =
n−k (−1)i k + 1i S(n + 1, k + i + 1), i=0
460
(8)
STIRLING, BELL, BERNOULLI, EULER, AND EULERIAN NUMBERS
where xn = x(x + 1) . . . (x + n − 1) (with x0 = 1) denotes the rising factorial power. The number of all partitions of a set with n elements is B(n) =
n
S(n, k),
(9)
k=1
called also a Bell number (or exponential number). These numbers verify the recurrence n
Data Loading...
