Đang chuẩn bị liên kết để tải về tài liệu:
concrete mathematics a foundation for computer science phần 5

số lượng các số nguyên tố không vượt quá n. Mỗi thủ đóng góp một yếu tố nhỏ hơn 2 "n! như vậy, như trước đây,Điều này thấp hơn bị ràng buộc là khá yếu, so với giá trị thực tế của z (n) n / nhà trọ, bởi vì logn là nhỏ hơn nhiều so n / logn khi n lớn. Nhưng chúng tôi không phải làm việc | 6 Special Numbers SOME SEQUENCES of numbers arise so often in mathematics that we recognize them instantly and give them special names. For example everybody who learns arithmetic knows the sequence of square numbers . . In Chapter 1 we encountered the triangular numbers 1 3 6 10 . . . in Chapter 4 we studied the prime numbers 2 3 5 7 . . in Chapter 5 we looked briefly at the Catalan numbers . . . In the present chapter we ll get to know a few other important sequences. First on our agenda will be the Stirling numbers and and the numbers these form triangular patterns of coefficients analogous to the binomial coefficients in Pascal s triangle. Then we ll take a good look at the harmonic numbers H and the Bernoulli numbers these differ from the other sequences we ve been studying because they re fractions not integers. Finally we ll examine the fascinating Fibonacci numbers and some of their important generalizations. 6.1 STIRLING NUMBERS We begin with some close relatives of the binomial coefficients the Stirling numbers named after James Stirling 1692-1770 . These numbers come in two flavors traditionally called by the no-frills names Stirling numbers of the first and second kind Although they have a venerable history and numerous applications they still lack a standard notation. We will write for Stirling numbers of the second kind and for Stirling numbers of the first kind because these symbols turn out to be more user-friendly than the many other notations that people have tried. Tables 244 and 245 show what and look like when n and k are small. A problem that involves the numbers 1 7 6 1 is likely to be related to k and a problem that involves 6 11 6 1 is likely to be related to just as we assume that a problem involving 1 4 6 4 1 is likely to be related to these are the trademark sequences that appear when n 4. 243 244 SPECIAL NUMBERS Table 244 Stirling s triangle for subsets. ini ini ini ini ini ini ini ini ini ini n tu 2J t3J l4J 15J 16J 7J 8J 0 1 1 0 1 2 3