(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

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