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