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
] prepared for:

ffice of Naval Research (Dr. Bruce McDonald)

FEDDOCS tatistics and Probability Branch

D 208.1 4/2: NPS-53BL77021 rlington, 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/2a2]

0-/27

2
where the mean u and the variance a are expressed in terms of the Bell

numbers B by
n

(2) V = Bn+1/Bn - 1

and

<3) °2 " Bn+2/B„ - (Bn+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) = / dtx / ■Ldt2.../ * ±(dKu1n/dupdtk

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 0 at one vertex to k at the opposite
vertex, the sectional areas normal to the diagonal cut by the hyper-
plane u=t..+t9+. •+£, 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!

0 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 0 £ u <_ 1 ,

(7) 2!g(u,2) = (1 - |u-l|) for 0 £ 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/sk = 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/ un_kg(u,k)du .

k 0

-2-

Using operation 82 of [6, p. 10] on the Laplace transform of

u

(11) k! / umg(u,k)du

0
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/sk .

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 )mdt

0 0 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) a2 = k/12 .

Using (14) the series

»t, , 2 2.ns , ks2/24 (ks2/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(-t2/2a2)

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)ksinhkS/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 — (?) / un kexp[-(u-k/2)Z/2aZ]du

2,„ 2

a/2TT 0

^3k 2,„

1 /n\ f /i /-> xn-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