NPS-53BL77021 NAVAL POSTGRADUATE SCHOOL Monterey, California ASYMPTOTIC REPRESENTATION OF STIRLING NUMBERS OF THE SECOND KIND by W. E. Bleick and Peter C. C. Wang // 9 February 1977 I 0A?97 r Approved for public release; distribution unlimited, .86 ] p repared for: ffice of Naval Research (Dr. Bruce McDonald) FEDDOCS tatistics and Probability Branch D 208.1 4/2: NPS-53BL77021 r li n gton, VA 22217 UDLCY KNOX LIBRARY .AVAL POSTGRADUATE SCHOOL :REY, CA 93940 NAVAL POSTGRADUATE SCHOOL Monterey, California Rear Admiral Isham Linder J. R. Borsting Superintendent Provost ABSTRACT: The distribution of the Stirling numbers S(n,k) of the second kind with respect to k has been shown by Harper [Ann. Math. Statist., 38 (1967), 410-414] to be asymptotically normal near the mode. A new single- term asymptotic representation of S(n,k), more effective for large k, is given here. It is based on Hermite's formula for a divided difference and the use of sectional areas normal to the body diagonal of a unit hypercube in k-space. A proof is given that the distribution of these areas is asymptotically normal. A numerical comparison is made with the Harper representation for n=200. This task was supported by: Contracts No. NR-042-286, NSWSES-56953, NISC-56969 NPS-53BL77021 9 February 1977 UNCLASSIFIED SECURITY CLASSl. ICATION OF THIS PAGE (When Data Entered) DUDLEY KNOX U8RARY NAVAL POSTGRADUATE SCHOOt MONTEREY. CA 93940 ^^ REPORT DOCUMENTATION PAGE READ INSTRUCTIONS BEFORE COMPLETING FORM 1. REPORT NUMBER NPS-53BL77021 2. GOVT ACCESSION NO 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) 5. TYPE OF REPORT & PERIOD COVERED Asymptotic Representation of Stirling Numbers of the Second Kind Technical Report 6. PERFORMING ORG. REPORT NUMBER 7. AUTHORfaj W. E. Bleick Peter C. C. Wang 8. CONTRACT OR GRANT NUMBER^,) NR-042-286 NSWSES-56953 NISC-56969 9. PERFORMING ORGANIZATION NAME AND ADDRESS Naval Postgraduate School Monterey, CA 93940 10. PROGRAM ELEMENT, PROJECT, TASK AREA ft WORK UNIT NUMBERS 11. CONTROLLING OFFICE NAME AND ADDRESS Office of Naval Research (Dr. Bruce McDonald) Statistics and Probability Branch Arlington, VA 22217 12. REPORT DATE 9 February 19 77 13. NUMBER OF PAGES 10 14. MONITORING AGENCY NAME » ADDRESSf// different from Controlling Office) 15. SECURITY CLASS, (of this report) UNCLASSIFIED 15a. DECLASSIFI CATION/ DOWN GRADING SCHEDULE 16. DISTRIBUTION ST ATEMEN T (of this Report) Approved for public release; distribution unlimited. 17. DISTRIBUTION STATEMENT (of the abstract entered In Block 20, If different from Report) 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverse aide If necessary and Identity by block number) Asymptotic representation Stirling numbers of the second kind Bell number Hermite's formula for a divided difference 20. ABSTRACT (Continue on reverse side It necessary and Identity by block number) The distribution of the Stirling numbers S(n,k) of the second kind with respect to k has been shown by Harper [Ann. Math. Statist., 38 (1967), 410-414] to be asymptotically normal near the mode. A new single-term asymptotic representa- tion of S(n,k), more effective for large k, is given here. It is based on Hermite's formula for a divided difference and the use of sectional areas normal to the body diagonal of a unit hypercube in k-space. A proof is given that the distribution of these areas is asymptotically normal. A numerical | comparison is made with the Harper representation for n=?00. DD FORM 1 JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE S/N 0102-014- 6601 | UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (When Data Bntarad) 1. Introduction. Previous asymptotic representations of Stirling numbers S(n,k) of the second kind have been of two types. One type has been a complete infinite series expansion as given by Hsu [1], and by Bleick and Wang [2] and [3]. A second type has been the single-term representation of S(n,k) given by Harper [4] as the normal distribution approximation (1) S(n,k)^— — exp[-(k-y) 2 /2a 2 ] 0-/27 2 where the mean u and the variance a are expressed in terms of the Bell numbers B by n (2) V = B n+1 /B n - 1 and < 3) ° 2 " B n + 2 /B „ - (B n + l /B „ )2 ' X • The purpose of this note is to give a new single-term asymptotic re- presentation based on Hermite's formula for a divided difference, and to compare it with that of Harper. 2. Use of Hermite's formula. A Stirling number S(n,k) of the second kind is defined as the kth difference of z at z=0 divided by kl. By [5, p. 10] we find that this divided difference can be represented by a formula of Hermite as the re- peated definite integral 1 t t . (A) S(n,k) = / dt x / ■ L dt 2 .../ * ± (d K u 1 n /dupdt k where u =t +t^+. .+t . We imagine that t , t„, .., t constitute a set of -1- rectangular Cartesian coordiantes and impose an orthogonal transforma- tion of coordinates to u , u„, .., u, . The volume of the space over which the integration in (4) is performed is a portion of a unit hyper- cube in k-space. If we allow the coordinate u to vary along the body diagonal of the hypercube from at one vertex to k at the opposite vertex, the sectional areas normal to the diagonal cut by the hyper- plane u=t..+t 9 +. •+£, from the domain of integration define a positive function g(u ,k) even with respect to the argument u..-ic/2. We take the integral of g(u..,k) to be k (5) / g(u ,k)du = 1/k! L to agree with the volume of the space over which the integration in (1) is performed. We drop the u.. subscript henceforth. Noting that g(u,k)=0 for k<u<0, we find that (6) g(u,l) = 1 for £ u <_ 1 , (7) 2!g(u,2) = (1 - |u-l|) for £ u £ 2 , and (8) 3!g(i :u,3)={ (3/2-|u-3/2|) 2 /2 for 1/2 < lu-3/2 I : 3/2 3/4 - (u-3/2) 2 for 1 < u < 2 . Consideration of the Laplace transforms of (6), (7) and (8) suggests that we conjecture the Laplace transform of k!g(u,k) to be (9) (l-e- s ) k /s k = e -ks/2 ( sinh s/2 k s/2 for all k. We demonstrate the truth of this conjecture later. On perform- ing the integration in (4) over the variables u , u , .., u we find oo (10) S(n,k) - k!A/ u n_k g(u,k)du . k -2- Using operation 82 of [6, p. 10] on the Laplace transform of u (11) k! / u m g(u,k)du we find the mth moment of the k!g(u,k) distribution about u=0 to be (12) lim (-lAd/ds) m (l-e" S ) k /s k . s-K) It is now easy to demonstrate the truth of the conjecture (9) by show- ing, with the aid of the multinomial theorem, that (12) is the same as the repeated integral 11 1 (13) / dt / dt .../ (t +t +. .+t ) m dt o z R over the volume of the hypercube. Use of (12) and (5) shows the variance of the k!g(u,k) distribution to be (14) a 2 = k/12 . Using (14) the series » t , , 2 2. ns , ks 2 /24 (ks 2 /24) 2 (15) exp (a s /2) = 1 + — =-j + - — ~-\ + • • is the bilateral, but not s multiplied, Laplace transform of the normal distribution (16) (l/a/2T)exp(-t 2 /2a 2 ) according to [7,p.2]]. The corresponding series for (9) multiplied by ks/2 e , or the bilateral Laplace transform of k!g(u,k) shifted left by k/2, is 2 2 2 (17) (2/s) k sinh k S /2 = [1 + SJi + LfUJtl + . . ] k . The dominant k power term in the coefficient of (s /4) in (15) is k /6 n! , and may be shown to be the same in the expansion of (17) by the use of the recurrence formula 6.361 of [8, p. 119]. This proves that the k!g(u,k) distribution is asymptotically normal as k-*». It is remarkable that the normal distribution should arise in the purely -3- geometrical context of sectional areas normal to the body diagonal of a hypercube of high dimension. On replacing k!g(u,k) in (10) by its Gaussian normal approximation 2 of mean u=k/2 and variance a =k/12 we find (18) S(n,k) a, -i — (?) / u n k exp[-(u-k/2) Z /2a Z ]du 2,„ 2 a/2TT ^3k 2,„ 1 / n \ f /i /-> x n-k -t 72. ^ — — (,) J (k/2-at) e dt . /2tT -°° 3. Numerical example. Table 1 compares the exact values of S(200,k) with the asymptotic approximations computed from the single-term representations (1) and o -J (. (18). Harper's representation (1), which uses B =.62475 10 ' u=49.975 and a=3.0551, gives an excellent fit near the mode (k=50) , but (18) gives a much better fit for large values of k. Asymptotic from (1) Table 1. Values of S(200,k) Exact Asymptotic from (18) 2 40 50 60 100 150 199 ,23135 10 39504 10 222 80347 10 69244 10 126 273 24458 10 273 42658 10 273 81579 10 37452 10 275 273 81493 10 .53533 10 275 273 .15285 10 .29658 10 277 274 ,49065 10 217 13938 10 43 .22839 10 30251 10 235 143 .27994 10 .30441 10 235 143 ,16955 10 -241 .19900 10- .19900 10" -4- REFERENCES 1. L. C. Hsu, Note on an asymptotic expansion of the nth difference of zero , Ann. Math. Statist. 19, (1948), 273-277. MR9 , 578. 2. W. E. Bleick and Peter C. C. Wang, Asymptotics of Stirling numbers of the second kind , Proc. Am. Math. Soc. 42 (1974), 575-580. 3. W. E. Bleick and Peter C. C. Wang, Erratum to 2 , Proc. Am. Math. Soc. 48 (1975), 518. 4. L. H. Harper, Stirling behavior is asymptotically normal , Ann. Math. Statist. 38 (1967), 410-414. 5. L. M. Milne-Thomson, The calculus of finite differences , MacMillan and Co., Ltd., London, 1933. 6. G. E. Rober ts and H. Kaufman, Table of Laplace transforms , Saunders, Philadelphia, 1966. MR32 #8050. 7. Balth. van der Pol and H. Bremmer, Operational calculus based on the two-sided Laplace integral , Cambridge University Press, 1955. 8. E. P Adams and R. L. Hippisley, Smithsonian mathematical formulae and tables of elliptic functions , Publication 2672, Smithsonian Institution, Washington, 1922. -5- DISTRIBUTION LIST Copies Copies Statistics and Probability program Office of Naval Research Attn: Dr. B. J. McDonald Arlington, Virgainia 22217 Director, Naval Research Laboratory Attn; Library, Code 2029 (ONRL) Washington, D. C. 20390 Defense Documentation Center Cameron Station Alexandria, Virginia 22314 Defense Logistics Studies Information Exchange Army Logistics Management Center Attn: Arnold Hixon Fort Lee, Virginia 23801 Technical Information Division Naval Research Laboratory Washington, D. C. 20390 Office of Naval Research New York Area Office 207 West 24th Street Attn: Dr. Jack Laderman New York, New York Director Office of Naval Research Branch Office 495 Summer Street Attn: Dr. A. L. Powell Boston, Massachusetts 02210 Director Office of Naval Research Branch Office 536 South Clark Street Attn: Dr. A. R. Dawe Chicago, Illinois 60605 Office of Naval Research Branch Office 536 South Clark Street Attn: Dr. Robert Buchal 3 Chicago, Illinois 60605 Director Office of Naval Research Branch Office 1030 East Green Street 6 Attn: Dr. A. R. Laufer Pasadena, California 91101 Office of -Naval Research 12 Branch Office 1030 East Green Street Attn: Dr. Richard Lau Pasadena, California 91101 Office of Naval Research 1 San Francisco Area Office 50 Fell Street San Francisco, California 94102 6 Technical Library Naval Ordanance Station Indian Head, Maryland 20640 Naval Ship Engineering Center Philadelphia 1 Division Technical Library Philadelphia, Pennsylvania 19112 Bureau of Naval Personnel Department of the Navy Technical Library Washington, D. C. 20370 1 Library, Code 0212 Naval Postgraduate School Monterey, California 93940 Library Naval Electronics Laboratory Center 1 San Diego, California 92152 -6- Copies Copies Naval Undersea Center Technical Library San Diego, California 92132 Applied Mathematics Laboratory Naval Ships Research and Development Center Attn: Mr. Gene H. Gleissner Washington, D. C. 20007 1 Office of .Chief of Naval Operations (Op 964) Ballston Tower No. 2 Attn: Mr. A. S. Rhodes Arlington, Virginia 22203 1 Naval Ships Systems Command Ships 0311 National Center No. 3 Attn: Miss B. S. Orleans Arlington, Virginia 20360 1 University of Chicago Department of Statistics Attn: Prof. W. Kruskal Chicago, Illinois 60637 1 Stanford University Department of Operations Research Attn: Prof. G. J. Lieberman Stanford, California 94305 1 Florida State University Department of Statistics Attn: Prof. I. R. Savage Tallahassee, Florida 32306 1 Florida State University Department of Statistics Attn: Prof. R. A. Bradley Tallahassee, Florida 32306 1 Princeton University Department of Statistics Attn: Prof. J. W. Tukey Princeton, New Jersey 08540 1 Princeton University Department of Statistics Attn: Prof. G. S. Watson Princeton, New Jersey 05840 Stanford University Department of Statistics Attn: Prof. T. W. Anderson Stanford, California 94305 University of California Department of Statistics Attn: Prof. P. J. Bickel Berkeley, California 94720 University of Washington Department of Mathematics Attn: Prof. Z. W. Birnbaum Seattle, Washington 98105 Harvard University Department of Statistics Attn: Prof. W. G. Cochran Cambridge, Massachusetts 02139 Columbia University Department of Civil Engineering and Engineering Mechanics Attn: Prof. C. Derman New York, New York 10027 Columbia University Department of Mathematics Attn: Prof. H. Robins New York, New York 10027 New York University Institute of Mathematical Science Attn: W. M. Hirsch New York, New York 10453 University of North Carolina Department of Statistics Attn: Prof. W. L. Smith Chapel Hill, North Carolina 27514 •7- Copies Cop university of North Carolina department of Statistics ttn: Prof. M. R. Leadbetter i.hapel Hill, North Carolina 27514 1 Purdue University department of Statistics Attn: Prof. H. Rubin . afayette, Indiana 47907 1 University of California San Diego Department of Mathematics P. 0. Box 109 Attn: Prof. M. Rosenblatt La Jolla, California 92038 1 New York University Department of Industrial Engineering and Operations Research Attn: Prof. J. H. K. Kao Bronx, New York 10453 1 University of Wisconsin Department of Statistics Attn: Prof. G. E. P. Box Madison, Wisconsin 53706 1 icate University of New York '■ hairman, Department of Statistics Attn: Prof. E. Parzen Buffalo, New York 14214 1 University of California Operations Research Center Attn: Prof. R. E. Barlow Berkeley, California 94720 1 Yale University Department of Statistics Attn: Prof. F. J. Anscombe New Haven, Connecticut 1 Purdue University Department of Statistics Attn: Prof. S. S. Gupta Lafayette, Indiana 47907 1 Cornell University Department of Operations Research Attn: Prof. R. E. Bechhofer Ithaca, New York 14850 Stanford University Department of Mathematics Attn: Prof. S. Karlin Stanford, California 94305 Southern Methodist University Department of Statistics Attn: Prof. D. B. Owen Dallas, Texas 75222 University of Georgia Department of Statistics Attn: Prof. R. E. Bargmann Athens, Georgia 30601 Daniel H. Wagner, Associates Station Square One Attn: Dr. L. D. Stone Paoli, Pennsylvania 19301 Daniel H. Wagner, Associates Station Square One Attn: Dr. B. Belkin Paoli, Pennsylvania 19301 Stanford University Department of Operations Research Attn: Prof. A. F. Veinott Stanford, California 94305 Stanford University Department of Operations Research Attn: Prof. D. L. Iglehart Stanford, California 94305 George Washington University Department of Statistics Attn: Prof. Herbert Solomon Washington, D. C. 20006 University of North Carolina Department of Statistics Attn: Prof. C. R. Baker Chapel Hill, North Carolina 27514 -8- Copies Copies Clemson University Department of Mathematics Attn: Prof. K. T. Wallenius Clemson, South Carolina 29631 1 University of California Department of Statistics Attn: Charles E. Antoniak Berkeley, California 94720 1 Clarkson College of Technology Division of Research Attn: Prof. M. Arozullah Potsdam, New York 13676 1 University of Southern California Electrical Sciences Division Attn: Prof. W. C. Lindsey Los Angeles, California 90007 1 Case Western Reserve University Department of Mathematics and Statistics Attn: Prof. S. Zacks Cleveland, Ohio 44106 1 University of Florida Department of Electrical Engineering Attn: Prof. D. G. Childers Gainesville, Florida 32601 1 Stanford University Department of Statistics Attn: Prof. H. Chemoff Stanford, California 94305 1 Naval Research Laboratory Electronics Division (Code 5267) Attn: Mr. Walton Bishop Washington, D. C. 20390 1 Commandant of the Marine Corps (Code AX) Attn: Dr. A. L. Slafkosky Scientific Advisor Washington, D. C. 20380 1 Program in Logistics The George Washington University Attn: Dr. W. H. Marlow 707 22nd Street, N. W. Washington, D. C. 20037 Mississippi Test Facility Earth Resources Laboratory (Code GA) Attn: Mr. Sidney L. Whitley Bay St. Louis, Mississippi 39520 Naval Postgraduate School Department of Operations Research and Administrative Sciences Attn: Prof. P. A. W. Lewis Monterey, California 93940 Southern Methodist University Department of Statistics Attn: Prof. W. R. Schucany Dallas, Texas 75222 Webb Institute of Naval Architecture Attn: Prof. 0. J. Karst Crescent Beach Road Glen Cove, New York 11543 University of Missouri Department of Statistics Attn: Prof. W. A. Thompson, Jr. Columbia, Missouri 65201 Rice University Department of Mathematical Sciences Attn: Prof. J. R. Thompson Houston, Texas 77001 University of California System Science Department Attn: Prof K. Yao Los Angeles, California 90024 Naval Postgraduate School Department of Mathematics Attn: P. C. C. Wang Monterey, California 93940 Naval Postgraduate School Department of Mathematics *\ttn: Prof. Willard Bleick 20 16 -9- Copies Copies Raytheon Company Submarine Signal Division Attn: Dr. W. S. Liggett, Jr. Portsmouth, Rhode Island 02971 1 Systems Control, Inc. Attn: Dr. L. P. Seidman 260 Sheridan Avenue Palo Alto, California 44306 1 University of California Department of Information and Computer Science Attn: Prof. E. Masry La Jolla, California 92037 1 University of California School of Engineering Attn: Prof. N. J. Bershad Irvine, California 92664 1 University of California School of Engineering and Applied Science Attn: Prof. I. Rubin Los Angeles, California 90024 1 Virginia Polytechnic Institute Department of Statistics Attn: Prof. C. Kramer Blacksburg, Virginia 24061 1 New York University Department of Electrical Engineering Attn: Prof. I. Yagoda Bronx, New York 10453 1 University of Rochester Depar* :ient of Statistics Attn: Prof. J. Keilson Rochester, New York 14627 1 University of Michigan Department of Industrial Engineering Attn: Prof. R. L. Disney Ann Arbor, Michigan 48104 1 Cornell University Department of Computer Science Attn: Prof. J. E. Hopcroft Ithaca, New York 14850 1 Smithsonian Institution Astrophysical Observatory Attn: Dr. C. A. Lundquist Cambridge, Massachusetts 02138 1 Naval Postgraduate School Department of Operations Research and Administrative Sciences Attn: Prof. J. D. Esary Monterey, California 93940 1 Polytechnic Institute of Brooklyn Department of Electrical Engineering Attn: Prof. M. L. Shooman Brooklyn, New York 11201 1 Union College Institute of Industrial Administration Attn: Prof. L. A. Aroian Schenectady, New York 12308 1 Ultrasys terns, Inc. Attn: Dr. D. C. Dorrough 500 Newport Center Drive Newport Beach, California 92660 1 University of New Mexico Department of Mathematics and Statistics Attn: Prof. W. J. Zimmer Albuquerque, New Mexico 87106 1 Princeton University Department of Statistics Attn: Prof. G. Simon Princeton, New Jersey 08540 1 Naval Ordnance Systems Command, NORD 035 Attn: Mr. 0. Seidman Room 6E08, National Center #2 Arlington, Virginia 20360 1 Naval Coastal Systems Laboratory Code P761 Attn: Mr. C. M. Bennett Panama City, Florida 32401 1 Food and Drug Administration Statistics and Information Science Division Health Protection Branch Attn: Dr. A. Petrasovits, Head, Survey Design and Quality Control 355 River Road, 4th Floor Vanier, Ontario, Canada 1 -10- QA297.5 .B6 Bleick Asymptotic representa- tion of Stirling num- bers of the second kind. 168307 ■■Rg-Sioo 3