.EQ
delim $$
define subar % "\o'|\(sb'" %
define CC % bold C %
define RR % bold R %
.EN
.de ST
.nf
.ta 6iR
	\(sq
.fi
..
.PH ""
.am DE
.sp
.ls 2
..
.nr Pt 1
.ce 99
.B
On the number of distinct block sizes in
partitions of a set
.R
.sp
.by
.sp
.I
A. M. Odlyzko
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
.I
L. B. Richmond
.R
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario N2L 3G1
Canada
.sp 2
.I
Abstract
.R
.sp
.ce 0
.P
The average number
of distinct block
sizes in a partition of a set of $n$
elements is asymptotic to $e~log~n$
as $n~->~inf$.
In addition, almost all partitions
have approximately $e~log~n$ distinct block sizes.
This is in striking contrast to the fact that
the average total number of blocks in a
partition is $wig~n( log~n) sup -1$ as $n~->~inf$.
.bp
.ce 99
.B
On the number of distinct block sizes in
partitions of a set
.R
.sp
.by
.sp
.I
A. M. Odlyzko
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
.I
L. B. Richmond
.R
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario N2L 3G1
Canada
.ce 0
.sp 3
.ls 2
.H 1 Introduction
A recent paper of
H. Wilf [6] compares the number of distinct
part sizes to the total number of parts in
various combinatorial partition problems.
.PH "''- \\\\nP -''"
.nr P 1
It is well known and easy to prove that the average number
of cycles of a permutation on $n$ symbols is
.DS 2
.EQ
log~n~+~gamma ~+~o(1)~~~roman as~~n~->~inf~,
.EN
.DE
when $gamma~=~0.577 "..."$ denotes Euler's
constant.
Wilf showed that the average
number of distinct cycle sizes in a permutation
on $n$ letters is
.DS 2
.EQ
log~n~+~gamma ~-~ Q~+~
o(1)~~~roman as~~n~->~inf~,
.EN
.DE
where
.DS 2
.EQ
Q~=~sum from n=2 to inf~
(-1) sup n over n!~
zeta (n)~=~0.65981 "..."~.
.EN
.DE
Thus in this case the numbers of parts and part
sizes are almost the same.
.P
The average number of parts in a partition
of an integer $n$ is known to be [3]
.DS 2
.EQ
wig~pi sup -1 (3/2) sup -1 n sup 1/2 ~log~n~~~roman as~~
n~->~inf~.
.EN
.DE
Wilf showed that the average number of distinct
part sizes in a partition of $n$ is
.DS 2
.EQ
wig~pi sup -1 6 sup 1/2 n sup 1/2~~~
roman as~~n~->~inf~.
.EN
.DE
Thus in this case the numbers of parts and of part
sizes grow at slightly different rates.
.P
The number of partitions of a set of $n$
elements into $k$ subsets is given by
$S(n,k)$, the Stirling numbers of the
second kind.
The asymptotics of the $S(n,k)$ were
known already to Laplace (see [1,5] for
extensive bibliographies), and it follows
from these asymptotic estimates that
the average number of blocks in a
partition of an $n$-element set is
.DS 2
.EQ
wig~n over {log~n}~~~roman as~~n~->~inf~.
.EN
.DE
(Wilf has pointed out that this result can also be
derived from the asymptotics of the Bell numbers
and the recurrence for the Stirling numbers.)
Wilf [6] derived a generating function
for $B(n,k)$, the number of partitions
of an $n$-element set with exactly
$k$ distinct block sizes, but he left
open the problem of estimating $b(n)$,
the average number of distinct block
sizes.
In this note we present two proofs that
.DS 2
.EQ
b(n)~~wig~~e~log~n~~~roman as~~n~->~inf~.
.EN
.DE
Thus in this case there is a great difference
between number of parts and part sizes.
We also indicate how both our proofs
can be easily adapted to show that
most of the time the number of distinct
part sizes is very close to $e~log~n$
(i.e., the normal order is $e~log~n$).
The first proof is
entirely self-contained apart from using
the well-known formula for the asymptotics
of the Bell numbers.
The second proof relies on the general
result of Hayman [4] about Taylor series
coefficients of analytic functions.
.P
In Section 2 we rederive Wilf's formula
for the generating function of the $B(n,k)$.
Our proofs are then presented in sections 3 and 4.
With additional work it might be possible to
obtain the complete distribution function of
the $B(n,k)$.
.H 1 "Generating functions and preliminaries"
We let $B(n,k)$ denote the number of partitions
of an $n$-element set that have exactly
$k$ distinct sizes of blocks, and we let
.DS 2
.EQ
B(n)~=~sum from k=1 to n~B(n,k)
.EN
.DE
be the $n$-th Bell number, the total
number of partitions.
(We remark in passing that $B(n,k)~=~0$
for $k$ larger than approximately
$(2n) sup 1/2$, which immediately
indicates that the average numbers of
blocks and block sizes have to be
very different.)
.P
Wilf's generating function for the
$B(n,k)$, which he derives from his
more general results [6], is
.DS 2
.EQ (2.1)
F(x,y)~=~
sum from {n,k >= 0}~
B(n,k) over n!~
x sup n y sup k~=~
prod from m=1 to inf~
"{" 1+y ( exp ( x sup m over m! ) -1 ) "}"~.
.EN
.DE
To prove it, we expand each of the exponentials
on the right side of (2.1), and expand the
product.
We find that the coefficient of $n! x sup n y sup k$
in the resulting
expansion is
.DS 2
.EQ (2.2)
sum ~ n! over
{prod from i=1 to k~l sub i ! (m sub i !) sup l sub i}~,
.EN
.DE
where the sum is over choices of
$l sub 1 , "..." , l sub k~>~0$,
$m sub 1 , "..." , m sub k~>~0$,
$sum ~l sub i m sub i~=~n$.
But each of the summands in (2.2)
is the number of ways of choosing
$l sub i$ blocks of size $m sub i$
from a set of $n$ elements when
the order of the blocks is irrelevant,
which proves (2.1).
.P
Setting $y~=~1$ in (2.1) gives
.DS 2
.EQ (2.3)
F(x,1)~=~sum from {n >= 0}~
B(n) over n!~x sup n~=~
exp ( e sup x -1)~,
.EN
.DE
the well-known generating function for the
Bell numbers.
.P
Define
.DS 3
.EQ
B sub 1 (n)~mark =~
sum from k~kB(n,k)~,
.EN
.sp
.EQ
B sub 2 (n)~=~sum from k~k sup 2 B(n,k)~.
.EN
.DE
Then
.DS 3
.EQ
sum from n~
{B sub 1 (n)} over n!~x sup n~mark =~
partial over {partial y}~
F(x,y) size 14 | sub down 10 y=1~=~
F(x,y)~cdot~
sum from m=1 to inf~ {exp ( x sup m over m! )-1} over
{1+ y ( exp ( x sup m over m! ) -1)} size 14 | sub down 10 y=1
.EN
.EQ (2.4)
~~~~~
.EN
.EQ
lineup =~
F(x,1)~sum from m=1 to inf~
(1- exp ( -~ x sup m over m! ) )~,
.EN
.DE
and similarly
.DS 3
.EQ
sum from n~
{B sub 2 (n)} over n!~x sup n~mark =~
partial over {partial y}~y~
partial over {partial y} ~F(x,y) size 14 | sub down 10 y=1
.EN
.sp
.EQ (2.5)
lineup =~
F(x,1) left [
"{"
sum from m=1 to inf~
(1- exp ( -~x sup m over m! ) ) "}" sup 2~+~
sum from m=1 to inf~
(1- exp ( -~ x sup m over m! ) )
.EN
.sp
.EQ
lineup~~~~~~~~~~~~~~~~~~~~ -~
left ""
sum from m=1 to inf~
(1- exp ( -~ x sup m over m! ) ) sup 2 right ]~.
.EN
.DE
.P
To prove our result about the average
number of block sizes, we will show
that
.DS 2
.EQ (2.6)
b(n)~=~{B sub 1 (n)} over B(n) ~wig~
e~log~n ~~~roman as~~n -> inf~.
.EN
.DE
To prove the result about normal
order, it is sufficient to show
that
.DS 2
.EQ (2.7)
{B sub 2 (n)} over B(n)~wig~
left ( {B sub 1 (n)} over B(n) right ) sup 2~,
.EN
.DE
since then the claimed result
follows from Chebyshev's inequality.
We do not present the details
of the proof of (2.7), since
they are analogous to the proofs of (2.6), although more involved.
.P
Before proceeding to the proofs, we
recall the asymptotic expansion of the Bell
numbers (more precise results are known,
see [2]):
.DS 2
.EQ (2.8)
B(n) over n!~=~1 over {e sqrt {2 pi}} ~exp
( {n+1} over u sub n~-~
(n+1) ~log~u sub n~-~
1 over 2 ~u sub n~+~o(1) )~~~roman as~~n~->~inf~,
.EN
.DE
where $u sub n$ is the unique positive root of
.DS 2
.EQ (2.9)
u sub n e sup u sub n~=~n+1~,
.EN
.DE
so that
.DS 2
.EQ (2.10)
u sub n~=~
log~n~-~
log~log~n~+~O ( {log~log~n} over {log~n} )~.
.EN
.DE
This result is obtained by using Cauchy's formula
.DS 2
.EQ
B(n) over n!~=~1 over {2 pi i n!} ~int from {| z | =u}~
F(z,1) z sup -n-1 dz
.EN
.DE
with $u~=~u sub n$.
.H 1 "First proof"
This proof shows, in essence, that the coefficient
of $z sup n$ in the Taylor series of
.DS 2
.EQ (3.1)
f sub k ( z)~=~
e sup {e sup z -1} ( 1 - e sup {- z sup k / k!} )
.EN
.DE
is approximately $B(n)/n!$ for $k~<=~e~log~n$
and is negligible for $k~>~e~log~n$.
.P
First we make some preliminary observations.
Since for $k~>=~1$
.DS 3
.EQ (3.2)
e sup z - 1~mark =~sum from n=1 to inf~
z sup n / n!~,
.EN
.sp
.EQ (3.3)
e sup z - 1 - z sup k / k!~lineup =~
sum from {n=1 from size 8 {n != k}}~ z sup n / n!~,
.EN
.DE
both have Taylor series coefficients that are $>=~0$,
we have for any $z~member~CC$,
.DS 2
.EQ (3.4)
| e sup z - 1-z sup k / k! |~<=~
e sup {| z |} - 1 - | z | sup k / k!~.
.EN
.DE
Similarly, since the Taylor coefficients
of (3.3) are $>=~0$ and less than or
equal to those of (3.2), if
.DS 2
.EQ (3.5)
exp ( e sup z - 1 - z sup k / k! )~=~
sum from m=1 to inf~
b(k,m) z sup m~,
.EN
.DE
then
.DS 2
.EQ (3.6)
0~<=~b(k,m)~<=~B(m)/m!~,
.EN
.DE
and
.DS 2
.EQ
| f sub k (z) |~<=~f sub k ( | z | )~.
.EN
.DE
.P
We now proceed to the main part of
the proof.
Fix any $epsilon~member~(0,10 sup -3 )$.
Consider
$k~<=~(e- epsilon ) log~n$, where $n$
is taken sufficiently large
(depending only on $epsilon$).
The coefficient of $z sup n$ in
$f sub k (z)$ is $B(n)- b (k,n)$.
By Cauchy's theorem,
.DS 2
.EQ
b(k,n)~=~1 over {2 pi i}~
int from {| z | = u sub n}~
exp ( e sup z - 1 - z sup k / k! ) z sup -n-1 dz~,
.EN
.DE
and so by (3.4)
.DS 3
.EQ
b(k,n)~mark <=~
u sub n sup {- n} ~max from {| z | = u sub n}~
| exp ( e sup z - 1- z sup k / k! ) |
.EN
.sp
.EQ
lineup =~
exp ( e sup u sub n - 1 - u sub n sup k /k! - n~log~u sub n )
.EN
.sp
.EQ
lineup =~
sqrt {2 pi}~
(n!) sup -1 B(n) exp ( log~u sub n + u sub n /2 - u sub n sup k /k!~+~
o(1 ) )
.EN
.sp
.EQ
lineup <=~(n!) sup -1 B(n) exp ( - u sub n /4 + o(1) )~~~roman as~~n -> inf ~,
.EN
.DE
since for $1~<=~k~<=~(e- epsilon ) ~log~n$,
$u sub n sup k /k!~>=~u sub n$
(for $n$ large enough).
Therefore the coefficient of $z sup n$
in the expansion of
.DS 2
.EQ
sum from {k <= (e - epsilon ) log~n}~
f sub k ( z )~=~e sup {e sup z -1} ~
sum from {k <= (e - epsilon ) log~n}~
(1- e sup {- z sup k / k! })
.EN
.DE
is
.DS 2
.EQ (3.7)
wig (e- epsilon ) (n!) sup -1 B(n)~log~n~~~roman as~~n~->~inf~.
.EN
.DE
Also, the corresponding coefficient for
the range $(e- epsilon )~log~n~<=~k~<=~(e+ epsilon )~log~n$
is in the range
$[0, 2 epsilon (n!) sup -1 B(n) ~log~n]$ by (3.6).
.P
It remains to deal with
$k~>=~(e+ epsilon )~log~n$.
If $k~>=~100~epsilon sup -1 ~log~n$, then by Stirling's
formula, on $| z |~=~u sub n$ we have
.DS 2
.EQ
| z sup k / k! |~=~
u sub n sup k over k!~<=~
( {e~log~n} over k ) sup k~<=~e sup -3k~,
.EN
.DE
and therefore
.DS 2
.EQ
| f sub k (z) |~<=~exp ( e sup {u sub n} -1-2k )~.
.EN
.DE
If $(e+ epsilon )~log~n~<=~k~<=~100 epsilon sup -1 log~n$,
then on $| z |~=~u sub n$,
.DS 2
.EQ
1- e sup {- z sup k /k!}~=~sum from {1 <= m <= 100 epsilon
sup -1 k sup -1 ~log~n}~
(-1) sup m-1 z sup km over (k!) sup m~+~
O( e sup {-50 ~log~n} )~.
.EN
.DE
Hence the coefficient of $z sup n$
in the Taylor expansion of
.DS 2
.EQ
sum from {k >= ( e + epsilon ) log~n} ~f sub k
(z)
.EN
.DE
is
.DS 3
.EQ
1 over {2 pi i}~
int from {| z | = u sub n}~
"{" sum from {k >= ( e + epsilon ) log~n}~
f sub k ( z ) "}" z sup -n-1 mark dz~ =~
.EN
.sp
.EQ
sum from {{k >= (e+ epsilon ) log~n} from size 8 {
k <= 100 epsilon sup -1 ~log~n}} ~
sum from m=1 to {100 epsilon sup -1 k sup -1 log~n}~
(-1) sup m-1 over {(k!) sup m}~
1 over {2 pi i}~
int from {| z | = u sub n}~
e sup {e sup z -1} z sup {km-n-1} dz
.EN
.sp
.EQ (3.8)
~~~~
.EN
.sp
.EQ
lineup
+O ( e sup {exp (u sub n ) -5 ~log~n - n~log~u sub n } )~,
.EN
.DE
and the last term above is
.DS 2
.EQ (3.9)
O left ( B(n) over n! ~n sup -4 right )~.
.EN
.DE
Again by Cauchy's theorem
.DS 2
.EQ (3.10)
1 over {2 pi i}~
int from {| z | = u sub n}~
e sup {e sup z -1 } z sup km-n-1 dz~=~
B(n-km) over (n-km)!~.
.EN
.DE
We now conclude the proof by showing that
.DS 2
.EQ
B(n-km) over {(k!) sup m (n-km)!}
.EN
.DE
is small when compared to $B(n)/n!$
(and $(e+ epsilon ) ~log~n~<=~k~<=~100 epsilon sup -1 log~n$,
$1~<=~m~<=~100 epsilon sup -1 $, say).
.P
Suppose that $(e+ epsilon ) ~log~n~<=~v~<=~10 sup 4 epsilon sup -2 log~n$.
Then by (2.8),
.DS 3
.EQ
log~
B(n-v)n! over B(n)(n-v)!~=~
-~ n+1 over u sub n~mark +~
n-v+1 over u sub n-v~+~
(n+1)~log~u sub n ~-~
(n-v+1)~log~u sub n-v
.EN
.EQ
lineup
+~u sub n /2 - u sub n-v /2 ~+~o(1)~.
.EN
.DE
Now by (2.10),
.DS 2
.EQ
u sub n-v ~=~
u sub n~-~v/n~+~O( v over {n~log~n} )~,
.EN
.DE
so
.DS 3
.EQ
log~
B(n-v)n! over B(n)(n-v)!~mark =~
(n+1) ( 1 over u sub n-v ~-~1 over
u sub n ) ~-~ v over u sub n-v ~+~
(n+1) ~log~u sub n over u sub n-v
.EN
.sp
.EQ
lineup +~
v~log~u sub n-v ~+~o(1)
.EN
.sp
.EQ
lineup =~
v~log ~u sub n~+~O (1)~.
.EN
.DE
Since for $n$ sufficiently large, and
$k~>=~(e + epsilon ) ~log~n$,
.DS 2
.EQ
log (k!) sup m~>=~m~
[k~log~k~-~(1+ epsilon /100 ) k ]~,
.EN
.DE
we finally obtain
.DS 3
.EQ
log~
left ( B(n-km)n! over {k! sup m B(n) (n-km)!} right )~mark <=~
km~log~u sub n ~-~
mk~log~k~+~
(1+ epsilon /100 ) km ~+~O(1)
.EN
.sp
.EQ
lineup <=~
km [ log~log~n~+~
o(1)~-~
log ( e+ epsilon ) ~-~log~log~n
.EN
.sp
.EQ
lineup~~~~~~~~ +~
( 1 + epsilon /100 ) ] ~+~ O(1)
.EN
.sp
.EQ
lineup <=~
- epsilon km/1000 ~<=~- epsilon 10 sup -3 log~n~.
.EN
.DE
Therefore
.DS 2
.EQ
sum from {{k > ( e + epsilon ) log~n} from size 8 {k <= 100 epsilon sup -1 log~n}}~
sum from
m=1 to {( 100 epsilon sup -1 log~n ) /k} ~
(-1) sup m-1 over (k!) sup m ~
1 over {2 pi i} ~
int from {| z | = u sub n } ~
e sup {e sup z -1 } z sup km-n-1 dz
.EN
.sp
.EQ (3.11)
=~O( B(n) over n!~
n sup {- epsilon /2000} ) ~.
.EN
.DE
It follows from (3.7)-(3.11) that
.DS 2
.EQ
{B sub 1 (n)} over B(n) ~wig~e~log~n
~~~~roman as~~~~n~->~inf~,
.EN
.DE
which completes our first proof.
.H 1 "Second proof"
We now prove our estimate using Hayman's
results [4] concerning admissible functions.
A function $f(z)$ is said to be admissible
if (we need only consider the case $f$ entire) with
.DS 3
.EQ
a(v)~mark =~
v~ {f prime ( v)} over f(v)~=~ {d ~log~f(v)} over {d~log~v}~,
.EN
.sp
.EQ
b(v)~lineup =~
va prime (v)~=~
{d sup 2 log~f(v)} over {d sup 2 log~v}~=~
v~ {f prime (v)} over f(v)~+~
v sup 2 ~
{f prime prime (v)} over f(v)~-~
v sup 2 ~ ( {f prime (v)} over f(v) ) sup 2~,
.EN
.DE
the following three conditions hold;
.sp
I) for some function $delta (v)$ with
$0~<~delta (v)~<~pi$,
.DS 2
.EQ
f(ve sup {i theta} ) ~wig~
f(v) e sup {i theta a(v) -  theta sup 2 b(v)/2}
,~~~roman as~~v~->~inf~,
.EN
.DE
uniformly for $| theta |~<=~delta (v)$, while
.sp
II) uniformly for $delta (v) ~<=~| theta |~<=~pi$
.DS 2
.EQ
f(ve sup {i theta} )~=~
o ( f(v) / sqrt {b(v)} ) ,~~~roman as~~
v~->~inf
.EN
.DE
and finally
.sp
III) $b(v)~->~inf~~~roman as~~v~->~ inf $.
.sp
.I
Lemma 1:
.R
The function
.DS 2
.EQ
f(z)~=~e sup {e sup z -1} ~sum from m=1 to inf~
(1- epsilon sup {- z sup m /m!} )
.EN
.DE
is admissible.
.sp
.I
Proof.
.R
The proof that III holds is immediate, since it is
easily seen that $b(v) ~wig~ v sup 2 e sup v$ as $v~->~inf$
for this function.
.P
We now establish that II holds for
$delta (v)~=~2 ~exp ( - 2 v/5 )$.
Let $m sub 0~=~m sub 0 (v)$ be the
largest integer such that
.DS 2
.EQ
v sup m over m!~>=~v~~~for~~m~<=~m sub 0~.
.EN
.DE
We note that $m sub 0~wig~ev$ as $v~->~inf$.
The argument of Section 3 shows that for
$m~<=~m sub 0$, $v~=~| z |$,
.DS 2
.EQ
| exp ( e sup z - 1 - z sup m /m! |~<=~
exp ( e sup v - 1 - v sup m /m!) ~<=~
exp ( e sup v - 1 -v )~.
.EN
.DE
Furthermore, if $z~=~v e sup {i theta }$,
$delta (v)~=~| theta |~<=~pi$, then for
large enough $v$,
.DS 3
.EQ
Re~e sup z ~mark =~
e sup {v ~cos~theta}
cos ( v~sin~theta )~<=~
exp ( v ~ cos~delta (v) )
.EN
.sp
.EQ
lineup <=~
exp ( v ( 1~-~1 over 3 delta (v) sup 2 ) )
.EN
.sp
.EQ
lineup <=~
exp ( v ( 1- e sup -4v/5 ) )~<=~
e sup v - v e sup v/5 ~,
.EN
.DE
so
.DS 2
.EQ
| exp (e sup z - 1 ) |~<=~
exp ( e sup v - 1 - v e sup v/5 )~.
.EN
.DE
Therefore for $m~<=~m sub 0$,
$z~=~v e sup {i theta}$,
$delta (v)~<=~| theta |~<=~pi$,
.DS 3
.EQ
| exp ( e sup z -1) ~-~
exp ( e sup z - 1 - z sup m /m!) |~mark <=~
exp ( e sup v - 1 ) ( exp ( -ve sup v/5 ) ~+~
exp ( -v ) )
.EN
.EQ (4.1)
~~~
.EN
.EQ
lineup <=~
2~exp ( e sup v - 1 - v )~.
.EN
.DE
Moreover for $m~>=~m sub 0$, $| z | sup m /m!~<~v$,
so
.DS 2
.EQ
| exp ( e sup z - 1 - z sup m /m!) |~<=~
| exp (e sup z -1) |~exp (v)~,
.EN
.DE
and thus
.DS 2
.EQ (4.2)
| exp ( e sup z - 1 )~ ( 1 - exp ( -z sup m /m!) |~<=~
2~ exp ( e sup v - 1 + v - ve sup v/5 )~.
.EN
.DE
Finally, if $m~>=~v sup 2$, then
.DS 2
.EQ (4.3)
| z sup m over m! |~=~ O( e sup -m )~,
.EN
.DE
and so
.DS 2
.EQ (4.4)
| exp ( e sup z - 1 )~ (1- exp ( -z sup m /m!) ) |~=~
O( exp ( e sup v - m ))~.
.EN
.DE
Applying (4.1) for $m~<=~m sub 0 $, (4.2) for
$m sub 0~<~m~<~v sup 2$,
and (4.3) for
$m~>=~v sup 2$, we obtain
.DS 2
.EQ
| exp ( e sup z - 1 ) ~
sum from m~
( 1- exp ( -z sup m /m!) ) |~=~O ( exp ( e sup v - v ))~,
.EN
.DE
which establishes II.
.P
To complete the proof of the lemma, we need to
show that I holds.
Since
.DS 2
.EQ
exp ( e sup {v e sup {i theta} }-1 ) ~wig~
exp ( e sup v - 1 + i theta a (v) - theta sup 2 b(v)/2)
.EN
.DE
as $v~->~inf$, uniformly for $| theta |~<=~delta (v)$,
it will suffice to show that if
.DS 2
.EQ
g(z)~=~sum from m~
(1- exp ( -z sup m /m!) )~,
.EN
.DE
then in that same range for $theta$,
.DS 2
.EQ (4.5)
g(z)~wig~g(v) ~~~roman as~~
v~->~inf~.
.EN
.DE
This part of the proof uses arguments similar
to those of Section 3.
Fix $epsilon~>~0$.
For $m~<=~(e- epsilon ) v$,
$| theta | ~<=~delta (v)$, $z~=~v e sup {i theta }$,
.DS 2
.EQ
Re ( z sup m /m!) ~=~
(m!) sup -1 v sup m ~cos~m~theta ~>=~1 over 2 ( m!) sup -1 v sup m~>=~
e sup {epsilon v /10}
.EN
.DE
for large $v$, so
.DS 2
.EQ (4.6)
1- exp ( -z sup m /m!)~=~1~+~O( e sup {- epsilon v } )~,
.EN
.DE
where the constant implied by the $O$-notation depends
only on $epsilon$.
Also, for $m~>=~( e + epsilon ) v $,
.DS 2
.EQ
| z sup m over m! |~=~
v sup m over m!~<=~e sup {- epsilon m /10}
.EN
.DE
for large $v$, so
.DS 2
.EQ (4.7)
1- exp ( -z sup m /m!)~=~O( e sup {- epsilon m/10} )~.
.EN
.DE
Finally, for $( e- epsilon )v ~<=~m ~<=~(e+ epsilon ) v$,
.DS 2
.EQ
Re ~z sup m~=~
v sup m ~cos ~m theta ~>~0~,
.EN
.DE
so
.DS 2
.EQ
| exp ( -z sup m /m!) | ~<=~1
.EN
.DE
and
.DS 2
.EQ (4.8)
| 1- exp (-z sup m /m!) | ~<=~2~.
.EN
.DE
Combining (4.5)-(4.7), we find that for
$| theta |~<=~delta (v)$,
.DS 2
.EQ
g( v e sup {i theta } ) ~=~e v ~+~
O( log~v ) ~.
.EN
.DE
Since this holds for all $epsilon~>~0$, we
obtain (4.5), and in fact even the more
precise statement that
.DS 2
.EQ (4.9)
g( v e sup {i theta } ) ~wig ~ e v
.EN
.DE
as $v~->~inf$, uniformly for
$| theta |~<=~delta (v)$.
.ST
.P
We can now prove our result by
applying Theorem I of [4], which
gives (using (4.9))
.DS 2
.EQ
{B sub 1 (n)} over n!~wig~
ev sub n over
{v sub n sup n ~ sqrt {2 pi b(v sub n )}} ~,
.EN
.DE
where $v sub n$ is defined by $a(v sub n )~=~n$.
Theorem I of [4] also implies that
.DS 2
.EQ
B(n) over n! ~wig~
{exp ( e sup {u sub n } -1)} over
{u sub n sup n sqrt {
2 pi ( u sub n + u sub n sup 2 ) exp ( u sub n )}} ~,
.EN
.DE
where $u sub n$ is defined by (2.9).
Stirling's formula implies that
.DS 3
.EQ
a ( v sub n )~mark =~
v sub n e sup v sub n ~+~
sum from m=1 to inf~
( ( m-1)! ) sup -1 v sub n sup m exp ( -v sub n sup m /m!)
g(v sub n ) sup -1
.EN
.EQ (4.10)
~~~
.EN
.EQ
lineup =~
v sub n e sup v sub n ~+~O ( v sub n sup {- 1/2 + epsilon } )~.
.EN
.DE
Next, (2.9) and (4.10) show that
.DS 2
.EQ
(v sub n - u sub n ) e sup v sub n ~+~
u sub n ( e sup v sub n - e sup u sub n )~=~O ( v sub n sup {- 1/2 + epsilon })~,
.EN
.DE
hence
.DS 2
.EQ
v sub n - u sub n~=~O ( e sup -v sub n v sub n sup {- 1/2 + epsilon } )~.
.EN
.DE
This implies that
.DS 3
.EQ
exp ( e sup v sub n ) ~mark =~
exp ( e sup u sub n + O ( v sub n sup {- 1/2 + epsilon )} ) ~=~
exp ( e sup u sub n ) ( 1+O ( v sub n sup {- 1/2 + epsilon } )) ~,
.EN
.sp
.EQ
v sub n sup n ~lineup =~
u sub n sup n ( 1 + O ( e sup -v sub n ) )~,
.EN
.DE
and that
.DS 2
.EQ
b(v sub n ) ~=~(u sub n + u sub n sup 2 ) e sup u sub n ( 1 +
O( e sup -u sub n ) )~.
.EN
.DE
Finally, we find that
.DS 2
.EQ
{B sub 1 (n)} over n!~wig~ev sub n ~ B(n) over n!~wig~
e u sub n ~B(n) over n! ~wig~
(e~log~n ) ~B(n) over n!~,
.EN
.DE
which is our result.
.PH ""
.bp
.ce
.B
REFERENCES
.R
.sp
.RL
.LI
E. A. Bender, Central and local limit theorems
applied to asymptotic enumeration, J. Comb.
Theory (A), \f215\f1 (1973), 91-111.
.LI
N. G. de Bruijn,
.ul
Asymptotic Methods in Analysis,
North-Holland, 1958.
.LI
P. Erdo\*:s and J. Lehner,
The distribution of the number
of summands in the partition of a
positive integer,
Duke Math. J. \f28\f1 (1941), 335-345.
.LI
W. K. Hayman, A generalization of Stirling's
formula, J. reine angew.
Math. \f2196\f1 (1956), 67-95.
.LI
V. V. Menon, On the maximum of Stirling numbers
of the second kind, J. Comb. Theory (A) \f215\f1 (1973),
11-24.
.LI
H. S. Wilf, Three problems in combinatorial asymptotics,
J. Comb. Theory (A), to appear.
.LE