Skip to main content
#
Full text of "Unique maximum property of the Stirling numbers of the second kind"

I LIFOKNIA U NPS-53BL77011 NAVAL POSTGRADUATE SCHOOL Monterey, California UNIQUE MAXIMUM PROPERTY OF THE STIRLING NUMBERS OF THE SECOND by KIND W. E. Bleick and Peter C. C. Wang 25 January 1977 Approved for public release; distribution unlimited. Prepared for: " -<r ice of Naval Research (Dr. Bruce McDonald) ti sties and Probability Branch D E £8°^:NPS.53BL77011 in 9 t0 "' VA 22217 NAVAL POSTGRADUATE SCHOOL Monterey, California Rear Admiral Isham Under J. r. Borsting Superintendent Provost ABSTRACT: Letting f (n) and £(n) the first and last maximum of the graph S(n,k);k - 1, 2, ... , n, Kanold [J. Reine Angew. Math 230(1968), 211-212] shows that, for sufficiently large n, n/log n < f(n) £ £(n) S n h(n)/log n with h(n) subject only to h(n)-*» as n->». This result was subsequently improved by Harborth [j. Reine Angew. Math 230(1968), 213-214] to yield lim f (n)n~ log n ■ lim *(n)n~ log n - 1. Together with n-*° n-H» Harper's result [Ann. Math. Stat. 38(1968), 410-414], it is concluded that S(n,k) have, asymptotically, a single maximum. Lieb [J. of Comb. Theory 5(1968), 203-206] shows that Stirling numbers of the second kind possess the property of Strong Logarithmic Concavity, and thus are unimodal. Dobson [J. of Comb. Theory 5(1968), 212-214 and Vol. 7(1969), 116-121] shows a similar result in a stronger form. However, the classical problem of establishing that S(n,k) possess a "unique" maximum for all n £ 3 remains unsolved. It is the purpose of this paper to provide the complete solution of this classical problem. This task was supported by: Office of Naval Research Contract No. NR-042-286 NPS-53BL77011 25 January 1977 UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) REPORT DOCUMENTATION PAGE READ INSTRUCTIONS BEFORE COMPLETING FORM 1. REPORT NUMBER NPS-53BL77011 2. GOVT ACCESSION NC 3 RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) Unique Maximum Property of the Stirling Numbers of the Second Kind 5. TYPE OF REPORT 4 PERIOD COVERED Technical Report 6. PERFORMING ORG. REPORT NUMBER i 7. AUTHORS W. E. Bleick Peter C. C. Wang 8. CONTRACT OR GRANT NUMBERfs) NR-042-286 9. PERFORMING ORGANIZATION NAME AND ADDRESS Naval Postgraduate School Monterey, CA 93940 10. PROGRAM ELEMENT, PROJECT. TASK AREA « 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 DAT; 25 January ]977 13. NUMBER OF PAGES 11 14. MONITORING AGENCY NAME ft ADDRESSf/f different from Controlling Office) 15. SECURITY CLASS, (of this report) UNCLASSIFIED 15«. DECLASSIFI CATION/ DOWN GRADING SCHEDULE 16. DISTRIBUTION STATEMENT (of this Report) Approved for public release; distribution unlimited. 17. DISTRIBUTION STATEMENT (of the abatract entered In Block 20, If different from Report) 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverse aide It naceaaary and Identify by block number) Stirling number of the second kind Unique Maximum property Hermite's formula for finite differences 20. ABSTRACT (Continue on reverae aide It naceaaary and Identity by block number) Letting f(n) and ^( n ) A tne first and last maxim*£aUof the graph S(n,k);k = 1, 2, ... , n, Kanold [J. Reine Angew. Math 230(1968), 211-212] shows that, for sufficiently large n, n/log n < f(n) < £(n) < n h(n)/log n with h(n) subject only to h(n)-*» as n-*°. This result was subsequently improved by Harborth [J. Reine Angew. Math 230(1968), 213-214] to yield lim f(n)n log n = lim £(n)n log n = 1. Together with Harper's result [Ann. n-x» n-*°° DD 1 JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE S/N 0102-014-6601 | UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (Whan Data Entered) UNCLASSIFIED ,L(_UK|TY CLASSIFICATION OF THIS PAGEC>W>en Dmta Entered) Math. Stat. 38 (1967), 410-414], it Is concluded that S(n,k) have, asymp- totically, a single maximum. Lieb [J. of Comb. Theory 5 (]968), 203-206] shows that Stirling numbers of the second kind possess the property of Strong Logarithmic Concavity, and thus are unimodal. Dobson [J. of Comb. Theory 5 (1968), 212-214 and 7 (1969), 116-121] shows a similar result in a stronger form. However, the classical problem of establishing that S(n,k) possesses a "unique" maximum for all n>3 remains unsolved. It is the purpose of this paper to provide the complete solution of this classical problem. UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGEfWhen Date Entered) I. Introduction The Stirling numbers of the second kind S(n,k) have come into renewed salience, primarily due to the fact that S(n,k) is the number of partitions of an n-set into k disjoint nonempty subsets and S(n,k) is the number of distinct fields defined on a finite sample space with n elementary events to which each field contains exactly k "£*" 2 events [1]. Letting f(n) and £(n) the first and last maxima A of the graph S(n,k);k = 1, 2, ... , n, Kanold [2] shows that, for sufficiently large n, n/log n < f(n) < i(n) 2 n h(n)/log n with h(n) subject only to h(n)-*» as n-*». This result was subsequently improved to yield lim f (n)n log n = lim £(n)n log n = 1, by Harborth [3]. Together with Harper's result [4], it is concluded that S(n,k) have, asymptotically, a single maximum. Earlier Lieb [5] shows that Stirling numbers of the second kind possess the property of Strong Logarithmic Concavity, and thus are unimodal. Dobson [6, 7] shows a similar result in a stronger form. However, the classical problem of establishing that S(n,k) possess ajl "unique" maximum for all n ^ 3 remains unsolved. It is the purpose of this paper to provide the complete solution of this classical problem. -1- II. Unique Maximum Property of S(n,k). In Riordan [8; p. 43] has given the Taylor series (1) £ S(n,k)z n ' k = Tf (l-jz)" 1 , n=k j=l convergent for |z| < k , as a generating function for the Stirling numbers S(n,k) of the second kind. The reciprocal transformation z = w converts (1) to the Laurent series (2) £ S(n,k)w" n = 7f (w-j)" 1 , n=k j=l convergent for |w| > k. The coefficient in the series (2) may be expressed as the contour integral (3) S(n,k) ■= 2ir± J (w-1) (w-2) . . . (w-k) where the contour C encloses the singular points of the integrand From (3) it follows that (4) S(n,k-1) - S(n,k) = Ar ( . vl^" 1 ^ n 2iri j (w-1) (w-2) ... (w-k) In Milne-Thomson [9;p.ll] we find that (4) is the divided difference [123.. k] of order k-1 of the polynomial (5) f (w) = w n - (k+1) w n_1 . -2- But by [9;p.l0] we find that (4) can also be represented by a formula of Hermite as the repeated definite integral (6) S(n,k-l)-9(n,k) -J 1 dt^ j'ldtj.... J^f (k_1) (u^dt^ where u=l+t..+t 9 +. .+t, _.. . We imagine that t. , t„, . . , t, _. constitute a set of rectangular Cartesian coordinates and impose an orthogonal transformation of coordinates to u.,u„, • . ,u» _ . We then perform the integration of (6) over the variables u„,u_, . . ,u, - . Because of the structure of the subspace ortho- gonal to u 1 we find that (6) becomes (7) S(n,k-1)-S(n,k) = J k f (k_1) (u^gCu^di^ - i r v " i f (k ' l) (v+5)g((i)d5 l-v where v=(l+k)/2=u -5 and g is a positive even function of £ independent of n. By differentiation of (5) we obtain (8) f (k_1) (u 1 ) = (n-l)![nu 1 n " k+1 -(n-k+l)(k+l)u 1 n " k ]/(n-k+l)l. On substituting (8) in (7) we find that the even part of the integrand is proportional to (9) g(f){nC[(v+5) n " k -(v-^ n " k ]-v(n-2k+2)[(v+ 5 ) n - k +(v- 5 ) n - k ]}. Since we are interested in finding more than one pair of n and k values which make (7) vanish, and since g(?) is independent of n, we see that (9) must be identically zero for all £. But (9) vanishes identically only for n=k=2. We have established the following Theorem: The Stirling numbers of the second kind S(n,k) possess a "unique" maximum for n>3. -3- References [1] Wang, Peter C. C, "Enumeration of Distinct Fields Over a Finite Probability Space", Notices of Amer. Math. Soc. 16(1969)294. [2] Kanold , H. J., "Uber line asymptotische Abschatzung bei Stirlingschen Zahlen 2. Art", J. Reine Angew. Math. 230(1968), 211-212. [3] Harborth, H. , "Uber das Maximum bei Stirlingschen Zahlen 2. Art", J. Reine Angew. Math. 230(1968), 213-214. [4] Harper, L. H. , "Stirling Behavior is Asymptotically Normal", Ann. Math. Stat. 38(1967), 410-414. [5] Lieb, E. H. , "Concavity Properties and a Generating Function for Stirling Numbers", J. of Comb. Theory 5(1968), 203-206. [6] Dobson, A. J.,, "A Note on Stirling Numbers of the Second Kind", J. of Comb. Theory, 5(1968), 212-214. [7] Dobson, A. J, and Rennie, B. C. , "On Stirling Numbers of the Second Kind", J. of Combinatorial Theory, 7(1969), 116-121. [8] Riordan, John, An Introduction tu Combinatorial Analysis , John Wiley & Sons, Inc* » 1958. [9] Milne- Thorns on, L. M. , The Calculus of Finite Differences , MacMillan and Co., Ltd., London, 1933. -4- DISTRIBUTION LIST 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 12 Copies Office of Naval Research Branch Office 536 South Clark Street Attn: Dr. Robert Buchal Chicago, Illinois 60605 Director Office of Naval Research Branch Office 1030 East Green Street Attn: Dr. A. R. Laufer Pasadena, California 91101 Office of -Naval Research Branch Office 1030 East Green Street Attn: Dr. Richard Lau Pasadena, California 91101 Office of Naval Research San Francisco Area Office 50 Fell Street San Francisco, California 94102 Technical Library Naval Ordanance Station Indian Head, Maryland 20640 Naval Ship Engineering Center Philadelphia Division Technical Library Philadelphia, Pennsylvania 19112 Bureau of Naval Personnel Department of the Navy Technical Library Washington, D. C. 20370 Library, Code 0212 Naval Postgraduate School Monterey, California 93940 Library Naval Electronics Laboratory Center San Diego, California 92152 -5- 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 -6- Copies Copies University of North Carolina Department of Statistics ' ttn: Prof. M. R. Leadbetter chapel Hill, North Carolina 27514 1 ,J urdue University department of Statistics \ttn: 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 State University of New York I nairman, 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 -7- 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. Chernoff 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 Attn: Prof. Willard Bleick 20 16 •8- 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 Ultrasystems, 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 -9- DUDLEY KNOX LIBRARY • RESEARCH REPORTS 5 6853 01071052 8