(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 "Asymptotic representation of Stirling numbers of the second kind"

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