Search the history of over 510 billion pages on the Internet.
Open Library
Full text of "Unique maximum property of the Stirling numbers of the second kind"
See other formats
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