\input amstex
\documentstyle{amsppt}
\define\squ{\qed}
\define\Cau{{1\over2\pi i}\oint}
\define\cau{{1\over2\pi i}\int}
\define\nn{{n!\over n^{n-1}}}
\define\doo{d\omega}
\define\CC{{\Cal C}}
\define\({\left(}
\define\){\right)}
\refstyle{A}
\widestnumber\key{F-G-T-88}
\hfuzz=20pt
% centre page in printer
\hoffset=1.5cm
\voffset=2.0cm
\topmatter
\title On Ramanujan's Q--Function${}^\dag$\endtitle
\author Philippe Flajolet, Peter J. Grabner,
Peter~Kirschenhofer and Helmut Prodinger\endauthor
\leftheadtext{P. Flajolet et al.}
\thanks\flushpar \dag Research of the four authors was supported
by the French Austrian scientific
cooperation pro\-gramme. % \newline
Work of P.~Flajolet was supported in part
by the ESPRIT~III
Basic Research Action Programme of the
E.C. under contract ALCOM~II (\#7141).
Work of P.~Grabner was supported
by the Austrian Science Foundation, Project Nr. P8274-PHY
\endthanks
\address
\hbox{\vbox{\hbox to 8 truecm{P. Flajolet\hfill\break}
\hbox to 8 truecm{Algorithms Project \hfill\break}
\hbox to 8 truecm{INRIA, Rocquencourt\hfill\break}
\hbox to 8 truecm{78153 Le Chesnay (France)\hfill\break}}
\vbox
{\hbox to 4.5 truecm{P.J. Grabner\hfill\break}
\hbox to 4.5 truecm{Technische Universit\"at Graz\hfill\break}
\hbox to 4.5 truecm{Steyrergasse 30\hfill\break}
\hbox to 4.5 truecm{A--8010 Graz (Austria)\hfill\break}}}
\medskip
\noindent
P. Kirschenhofer \& H. Prodinger\newline
Technische Universit\"at Wien\newline
Wiedner Hauptstra\ss{}e 8--10\newline
A--1040 Vienna (Austria)\endaddress
\abstract
This study provides a detailed analysis
of a function which Knuth
discovered to play a central r{\^ole}
in the analysis of hashing
with linear probing.
The function, named after Knuth $Q(n)$,
is related to several of Ramanujan's investigations.
It surfaces in the analysis
of a variety of algorithms and discrete probability prob\-lems including
hashing, the birthday paradox, random mapping
statistics, the ``rho'' method for integer factorization,
union--find algorithms, optimum caching, and the study of memory conflicts.
A process related to the
complex asymptotic methods of singularity analysis and saddle
point integrals permits to precisely quantify the behaviour of the
$Q(n)$ function.
In this way, tight bounds are derived.
They answer a question of Knuth
({\sl The Art of Computer Programming}, Vol.~1, 1968, [Ex.~1.2.11.3.13]),
itself a rephrasing of earlier questions of Ramanujan in 1911--1913.
\endabstract
\dedicatory Dedicated to D.~E.~Knuth, on the occasion of the 30th
Anniversary of his first analysis of an algorithm in 1962.\enddedicatory
\endtopmatter
\document
% \centerline{--- September $27$, $1992$ ---}
\centerline{--- August $25$, $1993$ ---}
%\smallskip\centerline{({\it Manuscript submitted to Journal of Algorithms\/})}
\smallskip\centerline{\ }
\heading 1. Introduction\endheading
In the 1911 issue of the Journal of the Indian Mathematical Society,
Ramanujan \cite{Ra11}
poses the following problem: {\sl Show that}
$${1\over2}e^n=1+{n\over1!}+{n^2\over2!}+\cdots+{n^n\over n!}\theta,
\qquad\hbox{\sl where $\theta$ lies between ${1\over2}$ and ${1\over3}$.}
\tag1.1$$
% where $\theta$ lies between ${1\over2}$ and ${1\over3}$''.}
A solution was then outlined in~\cite{Ra12}.
Later in his first letter to Hardy
dated January 16, 1913 (see \cite{Ra62, p.~xxvi},
\cite{Be69, p.~181} and \cite{Ha78}), Ramanujan
makes a stronger assertion, namely that
$$\theta={1\over3}+{4\over135(n+k)}
\qquad\hbox{\sl where $k$ lies between ${8\over45}$ and ${2\over21}$.}
\tag1.2$$
It is immediately clear nowadays, on probabilistic grounds, that the left hand side
member in (1.1) is approximated by the sum of the first $n$ terms
on the right. In fact, the sum $1+\cdots+n^{n-1}/(n-1)!$
multiplied by
$e^{-n}$ represents the probability that a
random variable with a Poisson distribution of mean $n$
be less than $n$. But by the Gaussian approximation of
Poisson laws of large mean, this probability is
close to ${1\over2}$ and the argument supplemented by
elementary real estimates
readily shows that $\theta\equiv\theta(n)=O(1)$.
Thus Ramanujan's assertions appear as asymptotic refinements
of a basic probabilistic observation.
Berndt's scholarly edition of Ramanujan's Notebooks contains a
complete bibliography on the original problem
which is closely related to Entries 47 and 48 of Chapter~12
(p.~179--184 of~\cite{Be89}) as well as to Entry 6 of Chapter~13
(p.~193--195 of~\cite{Be89}).
Berndt qualifies the
problem as {\sl ``an ultimately famous problem''}.
In his partial answer~\cite{Ra12} and in the notebooks,
Ramanujan provides in essence
a way of constructing an asymptotic expansion for $\theta\equiv\theta(n)$.
>From his analysis there results that $\theta(\infty)={1\over3}$ while
we have $\theta(0)={1\over2}$.
This, translated in terms of $k\equiv
k(n)$ says that
$k(\infty)={2\over21}$ and $k(0)={8\over45}$, and supported by a few
initial value computations, must have naturally led Ramanujan
to his assertion~(1.2).
A solution to the weaker inequality (1.1) was given by G.~Szeg\H o in
1928~\cite{Sz28}, and almost simultaneously Watson~\cite{Wa29}
wrote a paper where he proved~(1.1) and adds regarding~(1.2):
{\sl `` I shall also give reasons, which seem to me fairly
convincing, for\/ {\rm believing} that $k$ lies between $8/45$ and
$2/21$.''}
Our purpose here is to finally provide a complete proof of
Ramanujan's assertion~(1.2).
In 1962, which is exactly 50 years after Ramanujan's
original note~\cite{Ra12}
and 75 years after Ramanujan's birth, Knuth conducted his first average--case
analysis of an algorithm, namely the analysis of
{\sl hashing with linear probing} (see the footnote on page~529
of~\cite{Kn73}).
That analysis is given in full in Volume 3 of
{\sl The Art of Computer Programming} \cite{Kn73} and,
in Volume~1, Knuth uses it as an illustration
of asymptotic analysis techniques \cite{Kn68, p.113}.
A key r\^ole in the analysis is played by a function closely related
to $\theta(n)$, the $Q(n)$--function, and
in Exercise~1.2.11.3.13,
Knuth asks for a final solution to Ramanujan's problem~(1.2).
The variant form used
by Knuth introduces the two functions
$$\aligned Q(n)&=1+{n-1\over n}+{(n-1)(n-2)\over n^2}+\cdots\cr
R(n)&=1+{n\over n+1}+{n^2\over (n+1)(n+2)}+\cdots,\endaligned\tag 1.3$$
and one finds easily
$$Q(n)+R(n)=n!e^n/n^n.$$
Thus $Q(n)$ and $R(n)$ are closely related, and the asymptotics of one of them determines the other.
The relation of Knuth's definition (1.3) to Ramanujan's problem
should also be clear, considering the equality
$${n^n\over n!}Q(n)={n^{n-1}\over(n-1)!}+{n^{n-2}\over(n-2)!}+\cdots+1
,\tag 1.4$$
which entails
$${n^n\over n!}Q(n)={1\over2}e^n-\theta{n^n\over n!}
\qquad\hbox{and}\qquad
\theta(n)={1\over2}(R(n)-Q(n)).$$
In this way, Ramanujan's problem can be rephrased as:
{\sl ``Show that
$$R(n)-Q(n)={2\over3}+{8\over135(n+k)}$$
where $k\equiv k(n)$ lies between $2\over21$ and $8\over45$''.}
Following Knuth,
this is the form that we shall take as our starting point,
setting $D(n)=R(n)-Q(n)$,
so that $D(n)=2\theta(n)$.
The approaches followed by Ramanujan himself and later authors
all make use of {\sl real} integral representations
derived from
$$Q(n)=\int_0^\infty e^{-x}\big(1+{x\over n}\big)^n\,dx,\tag 1.5$$
and proceed using the Laplace method for the asymptotic
evaluation of integrals~\cite{DB81}.
>From this representation, $Q(n)$ is up to normalization an incomplete
gamma function, a ${}_1F_1$--hypergeometric, and accordingly, it
admits an explicit continued fraction representation of the Gauss
type, as already noticed by Ramanujan (Entry 47 in Chapter~12 of
\cite{Be89}).
% The mathematical literature available on this problem
% is scholarly reviewed in Berndt's edition of Ramanujan's
% notebooks~\cite{Be89} to which
% we refer for all references. (Observe also the related Entry~6 of Chapter~13.)
% We shall work instead with a {\sl complex\/} integral representation
% that derives from a generating function of the $Q(n)$.
As a historical fantasy, it may be of interest to observe that,
quite possibly, Ramanujan was led to his conjecture by considerations
related to the distribution of prime divisors in integers.
The Erd\H os-Kac Theorem asserts that,
for integers, the `number-of-divisors'
function is asymptotically Gaussian distributed over large ranges.
A form of this theorem
does appear in Ramanujan's notes, under a
Poisson formulation:
{\sl The number of integers less than $n$ with
numbers of prime divisors at most $k$ is asymptotically
$${x\over\log x}\bigg[1+{\log\log x\over 1!}+{(\log\log x)^2\over 2!}+\cdots+
{(\log\log x)^k\over k!}\bigg].$$}
Letting $k$ vary with $n$ in the ``interesting''
region $k\approx\log\log x$ naturally leads to questions like (1.1).
It should also be said at this stage that, apart from sentimental value,
the $Q(n)$ function appears in a number of problems in
discrete probability and the analysis of algorithms:
\roster
\item $1+Q(n)$ is the expected number of persons
it takes in order to find two having the same birth date
(when the year has $n$ days!). This is the
classical birthday problem which is of interest
in random allocations and general
hashing algorithms (see Section~4.1 of
\cite{Kn73} or \cite{FGT92}).
For instance, on earth,
it takes on average only 24.61658 persons to find two
with the same birth date.
\item The analysis of hashing with linear probing,
when the table is full, is expressed simply in terms of $Q(n)$.
The cost of a successful search is
about ${1\over2}\sqrt{\pi n\over2}$, as results from the asymptotic
analysis of $Q(n)$
(see~\cite{Kn73, p.~530} and \cite{VF90, p.~509--511}).
\item Random mapping statistics involve $Q(n)$ in several places,
in relation to their cycle structure. There is a vast
literature on this topic, see~\cite{Kn69, p.~8} for the basic results,
\cite{KP89} for related problems,
and~\cite{FO90a} for a recent survey of random mapping statistics.
The corresponding analyses are also relevant
to the study of random number generators \cite{Kn69, Sec.~3.1}.
It is starting from there that Pollard conceived one of his
integer factorization algorithms, the well known ``rho method'',
which itself permitted in its time the discovery of
the factorization of the eighth Fermat number $F_8=2^{2^8}+1$.
\item Analysis of Union--Find algorithms under the random spanning
tree model essentially depends on $Q(n)$ \cite{KS78}.
\item Analysis of optimum caching \cite{Kn85}
and the study of
memory conflicts or deadlocks \cite{KR75,CR92} involve the function $Q(n)$.
\endroster
The paper is organized as follows.
Section~2 develops a complex
integral representation based on a generating
function of the $Q(n)$ from which yet another proof of its asymptotic
expansion follows.
Our approach is in fact a hybrid of singularity analysis
and saddle point in the following sense:
It starts with an integral representation
based on an expansion essentially dictated by the singularity
analysis method (see Eq.~(2.4), and the proof of Proposition~2); then
a suitable change of variable is introduced that causes the
integration contour to pass through
a saddle point (see Eq.~(2.5),(3.1),(3.2) and the
developments at the beginning of Section~3).
In Section~3, effective error bounds for the intervening
integrals are developed.
The various lemmas and estimates are then woven together
in Section~4, where
the proof of the main inequality is completed. Section~5 offers a few
hindsights.
\heading 2. Generating Functions, Asymptotics, and an Integral
Representation\endheading
An important function in combinatorial analysis is the function $y(z)$ defined
implicitly by the equation
$$y(z)=ze^{y(z)},\tag2.1$$
with $y(z)=z+z^2+3z^3/2+\cdots$.
By the Lagrange inversion formula, we have\footnote {We let $[z^n]f(z)$ denote
the coefficient of $z^n$ in the Taylor expansion of $f(z)$.}
\proclaim{Proposition 1} The Taylor coefficients of $y(z)=ze^{y(z)}$
and its powers are given by
$$[z^n]y(z)={n^{n-1}\over n!} \qquad\hbox{and}\qquad
[z^n]y^k(z)=k {n^{n-k-1}\over (n-k)!}.\tag2.2$$
Furthermore, a generating function of $Q(n)$ is expressible in terms
of $y(z)$:
% $$Q(n)={n!\over n^{n-1}}[z^n]\log{1\over 1-y(z)}\,.\tag2.3$$
$$\sum_{n=1}^\infty Q(n)n^{n-1}{z^n\over n!}=\log{1\over 1-y(z)}\,.\tag2.3$$
\endproclaim
The well known expansions (2.2) go back to
Legendre and Eisenstein.
The companion facts from combinatorics
are classical (see \cite{GJ83} or \cite{FO90a}):
$y(z)$ is the exponential generating function (EGF) of rooted labelled
trees and
the function appearing in (2.3), $L(z)=\log(1-y(z))^{-1}$, is the EGF
of functional graphs (mappings) that are connected.
Thus, $Q(n)/n$ also represents the probability that a random mapping be
connected, a result already known to R\'enyi and Harris.
Equation (2.3) has already appeared
in the literature~\cite{KS78,FO90a,KP89,VF90}. It constitutes
the starting point of a transparent analysis
of the asymptotics of $Q(n)$.
In this way, we rederive through generating functions the
asymptotic expansion of $Q(n)$ known from the works of Ramanujan, Watson, and
Knuth~\cite{Be89,Wa29,Kn68}.
\proclaim{Theorem~1}{\rm [Ramanujan, Watson, Knuth]}
The quantities $Q(n),R(n)$ admit full asymptotic expansions in
descending powers of $\sqrt{n}$:
$$
Q(n)\sim \sqrt{\pi n\over2}-{1\over3}+{1\over12}\sqrt{\pi\over2n} -
{4\over135n}+ \cdots
$$
$$
R(n)\sim \sqrt{\pi n\over2}+{1\over3}+{1\over12}\sqrt{\pi\over2n} +
{4\over135n}+ \cdots\,.
$$
\endproclaim
\demo{Proof}
We sketch here the proof based on singularity analysis
(see~\cite{VF90,KP89,FO90a} for related developments).
The implicitly defined function $y(z)$ has a singularity
of the square--root type at $z=1/e$, and
$$y(z)=1-\varepsilon+{1\over3}\varepsilon^2-{11\over72}\varepsilon^3
+{43\over540}\varepsilon^4-\cdots,\qquad\varepsilon=\sqrt{2-2ez},
$$
% $$y(z)\sim 1-2^{1/2}\sqrt{1-ez}+{2\over3}(1-ez)-\cdots
as $z\to e^{-1}$. This induces
a logarithmic singularity for $L(z)$ at $z=1/e$,
$$L(z)=\log{1\over\varepsilon}
+{1\over3}\varepsilon-{7\over72}\varepsilon^2+
{133\over3240}\varepsilon^3+\cdots
={1\over2}\log(1-ez)^{-1}+\cdots\,.$$
By singularity analysis \cite{FO90b},
the asymptotic equivalent of $L(z)$ transfers to the coefficients,
which gives $[z^n]L(z)\sim{1\over2} e^{n}n^{-1}$, and
$Q(n)\sim \sqrt{\pi n/2}$.
The full expansion of $L(z)$ in powers of $(1-ez)^{1/2}$
also
translates into a full asymptotic expansion of
$Q(n)$ in powers of $n^{1/2}$. The developments for $R(n)$ are
entirely similar.
\qed\enddemo
In preparation for the more detailed treatment
involving bounds for $D(n)$, we
next need to make fully explicit the
various expansions and representations related to its generating function.
We have $Q(n)+R(n)=n!e^n/n^{n}$
so that a generating function of $D(n)$ is
$$\sum_{n=1}^\infty D(n)n^{n-1}{z^n\over n!}=\log{(1-y)^2\over
2(1-ez)}.$$
Appeal to
% Thus, we proceed instead from
Cauchy's integral formula for coefficients
of analytic functions. When applied to (2.3), it gives
% $$Q(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{1\over 1-y(z)}\,d\omega
$$D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y(z))^2\over 2(1-ez)}\,d\omega
\qquad\hbox{with}\qquad d\omega={dz\over z^{n+1}},\tag2.4$$
where $\Cal C$ is a sufficiently small countour surrounding the origin.
% We mentioned earlier
% % shortly after
% (1.3) that $Q(n)+R(n)=n!e^n/n^{n}$. Thus
% $$Q(n)+R(n)=n!/n^{n-1}[z^n]\log(1-ez)^{-1},$$ from which we derive:
% $$D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y)^2\over 2(1-ez)}\,{dz\over z^{n+1}}.\tag2.6$$
%
A key step is now to allow $y$ to be taken as
the independent variable (this is precisely inspired by
the analytic proof of the Lagrange inversion
theorem) so that $z=ye^{-y}$.
The result is an alternative form of Eq.~(2.4).
\proclaim{Proposition 2} Quantity $D(n)=R(n)-Q(n)$ satisfies
$$
D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y)^2\over 2(1-ye^{1-y})}\,
d\omega \quad\text{with}~~
\doo=\frac{dz}{z^{n+1}}=(1-y)e^{ny}\frac{dy}{y^{n+1}}, \tag 2.5
$$
where $\Cal C$ is a small contour around the origin in either
the $z$--plane (the first form of $d\omega$ is used with $y$
implicitly defined by $y=ze^y$)
or in the $y$--plane
(the second form is used with $y$ being the independent variable).
\endproclaim
In order to make use of~(2.5), we first observe that, from (2.2),
the coefficients of $(y-1)^k$ form an
asymptotic scale:
$$\gathered\nn [z^n](y-1)=1,\quad \nn [z^n](y-1)^2=-{2\over n},\cr
\nn [z^n](y-1)^3=-{3\over n}+{6\over n^2},\quad
\nn [z^n](y-1)^4={20\over n^2}-{24\over n^3},\cr
\nn [z^n](y-1)^5={15\over n^2}-{130\over n^3}+{120\over n^4},\quad
\ldots\endgathered\tag2.6$$
with $n!n^{-n-1}[z^n](y-1)^k$ being $O(n^{-\lfloor k/2\rfloor})$ and comprising $\lceil k/2\rceil$ terms.
If we expand the integrand of~(2.5) in powers of $(y-1)$ and use the
{\sl first\/} form of $d\omega$,
$d\omega=dz/z^{n+1}$, then through (2.6) we
get an asymptotic expansion for $D(n)$:
$$D(n)\sim \sum_{k\ge 1}c_k\cdot[z^n](y-1)^k\tag2.7$$
where ($\delta =y-1$):
$$\aligned &\log{\delta ^2\over 2
(1-(1+\delta )e^{-\delta })}=\sum_{k\ge1} c_k \delta ^k\cr
& ={2\over3}\delta-{1\over36}\delta^2-{1\over810}\delta^3+
{1\over12960}\delta^4\cr
&\ \ +{1\over68040}\delta^5+{1\over12247200}\delta^6-{1\over6123600}\delta^7
-{13\over1175731200}\delta^8+\cdots.\endaligned\tag 2.8$$
By~(2.6), Eq.~(2.7) itself transforms into a standard expansion,
$$D(n)\sim\sum_{k\ge0} {d_k \over n^k},\tag2.9$$
whose first few terms are
$$D(n)\sim {2\over 3}+{8\over 135 n}-{16\over 2835 n^2}-{32\over 8505 n^3}+{1794\over 12629925 n^4}+\cdots .$$
Analytically, the
complete process leading to~(2.9) is again justified by the
singularity analysis theorems.
It is quite parallel to the proof of Theorem~1 (only $y-1$ is used instead of
the asymptotically related $\varepsilon$) and refinements of it
are going to provide the required bounds.
\heading 3. Expansions with Effective Error Bounds
\endheading
The main device employed here follows the outline given in the equations
(2.7)--(2.9).
We use a {\sl terminating\/} form of (2.8) inside our main integral
representation,
$${n^{n-1}\over n!}D(n)=\Cau_{\Cal C}\bigg(\sum_{k=0}^K c_k (y-1)^k \bigg)\,\doo
+\Cau_{\Cal C} R_{K}(y-1)\,\doo,\tag3.1$$
where the $c_k$ are defined by (2.8) and
$$R_{K}(y-1)=\log{(1-y)^2\over 2(1-ye^{1-y})}-\sum_{k=1}^K c_k (y-1)^k
=\sum_{k\ge K+1}c_k(y-1)^k.\tag3.2$$
The integral with the finite sum in (3.1) is known {\sl exactly} from
Section~2 and Eq.~(2.6); our aim is
to derive constructive bounds for the integral containing the remainder.
To estimate the remainder integral, we make use the
{\sl second\/} form of $d\omega$, namely $d\omega=(1-y)e^{ny}dy/y^{n+1}$
together with a contour
{\sl in the $y$--plane} whose choice is dictated by a {\sl saddle
point heuristic}.
The quantity $e^{ny}y^{-n}$ has a saddle point at $y=1$ with axis
perpendicular to
the real line; accordingly, we take $\CC=\CC_1\cup\CC_2$ where
$$\CC_1=\big\{1+i\tau\ /\ -1\le \tau\le 1\big\}
\ \ \hbox{and}\ \
\CC_2=\big\{y\ /\ |y|=\sqrt2,\ \Re(y)\le1\big\}.\tag3.3$$
Our proof,
that will eventually fix $K=10$, consists of two simple phases.
\roster
\item"(a)" The integral of the remainder term along $\CC_2$ is small
since there $y^{-n}=O(2^{-n/2})$;
in addition, it can be effectively bounded.
\item"(b)" Along $\CC_1$, quantity $R_{K}$ is small since it was
obtained by subtracting from
a function the first $K$ terms of its locally convergent Taylor
expansion;
in addition, constructive bounds can be derived.
\endroster
\topinsert
\vskip 7.5cm
\special{psfile=rama1.ps hscale=42 vscale=42 hoffset=0}
\special{psfile=rama2.ps hscale=18 vscale=18 hoffset=230}
\vskip0.3cm
\noindent
{\bf Figure~1.} The transform by $f(z)$ of the square of
side $2\pi$ centered at the origin together with a blow up of the
picture near the origin (lower right).
\medskip\noindent\hrule\medskip
\endinsert
We thus proceed with this programme, starting with
estimates of the $c_k$ coefficients,
continuing with the estimates along $\CC_2$ then $\CC_1$, which
we give for a general $K$. To take care of recurring factors
of the form $n!/n^n$, we appeal to a weak form of Stirling's formula
valid for all $n\ge1$,
$$n!<{\textstyle 11\over 10} n^n e^{-n}\sqrt{2\pi n}.\tag3.4$$
\proclaim{Lemma 1} For all $k\ge1$, we have
$$|c_k|<{10.96714833\over \pi^k}.\tag3.5$$
\endproclaim
\define\QQQ{{\Cal Q}}
\demo{Proof}
>From Eq.~(2.8) We estimate the coefficients of $\log f(z)$
where
$$f(z)=\frac{z^2}{2(1-(z+1)e^{-z})}$$
by means of Cauchy's formula:
$$c_k=\Cau_\QQQ\log f(z)\frac{dz}{z^{k+1}},\tag3.6$$
where $\QQQ$ is any small enough simple contour encircling the origin.
We propose to take here as contour $\QQQ$ the boundary of the square
$|\Re z|\leq\pi$, $|\Im z|\leq\pi$.
First, elementary computations
show that there are no zeros nor poles of $f(z)$ within $\QQQ$.
The graph of Figure~1 which represents the image of $\QQQ$ by $f(z)$
confirms this via the principle of the argument since $f(\QQQ)$ has
winding number~0 with respect to the origin.
Thus $\log f(z)$ is analytic in and on $\QQQ$ and the Cauchy
integral~\thetag{3.6}
for $c_k$ can be evaluated by taking $\QQQ$ as the integration contour.
By considering the four sides of the square $|\Re z|\leq\pi$, $|\Im z|\leq\pi$
and using trivial estimates we obtain:
$$\frac{\pi^2}{2(1+(2\pi+1)e^\pi)}\leq\left|f(z)\right|\leq
\frac{\pi^2}{1-(\pi+1)e^{-\pi}}.$$
We next have to consider the argument of $f(z)$.
For this purpose we investigate
the argument of the denominator of $f(z)$. We restrict our investigation
to the part of the square with $\Im z>0$. By examining the behaviour of the sign
of the real and imaginary part of $g(z)=1-(z+1)e^{-z}$ on the three lines
$\Re z=\pi,0\leq\Im z\leq\pi$, $-\pi\leq\Re z\leq\pi,\Im z=\pi$ and
$\Re z=-\pi,0\leq\Im z\leq\pi$, we find that $g(z)$ does not enter the
third quadrant. Thus we have $-\frac\pi2<\arg g(z)<\pi$. On the other hand
we have $0\leq\arg z^2\leq2\pi$. Combining the two bounds yields
$$|\arg f(z)|\leq\frac52\pi.$$
Thus we obtain
$$\left|\log f(z)\right|\leq\(\log^2\frac{\pi^2}{2((2\pi+1)e^\pi+1)}+\frac{25}4\pi^2\)^{\frac12}=8.613578\ldots.$$
Bounding the integral~\thetag{3.6} trivially, we arrive at
$$|c_k|\le {1\over2\pi}\left({8.613578\over \pi^{k+1}}\right)(8\pi),$$
which is equivalent to \thetag{3.5}.
\qed\enddemo
% The proof is split into two parts: We first show that there are no zeros
% or poles of
% $$f(z)=\frac{z^2}{2(1-(z+1)e^{-z})}$$
% in the strip $|\Im z|\leq\pi$; then we show estimates for $f(z)$ on the
% boundary of the square $|\Re z|\leq\pi$, $|\Im z|\leq\pi$ and use these
% estimates and Cauchy's formula to prove \thetag{3.5}.
%
% Trivially we have to consider only the denominator of $f(z)$. We set $z=u+iv$,
% split the equation $1-(z+1)e^{-z}=0$ into real and imaginary part and obtain
% the system of equations
% $$\align &1+u=e^u\cos v\cr&v=e^u\sin v.\endalign$$
% It is easy to see that this equations have no solution for $|v|\leq\pi$
% except $u=v=0$. This corresponds to $z=0$ which is not a zero of $f(z)$.
% Thus $\log f(z)$ has no singularity in the strip $|\Im z|\leq\pi$.
Numerical computations
suggest that the $c_k$ decrease roughly like $7^{-k}$, so
that the estimate of Lemma~1 is not too tight.
It is however amply sufficient for our purposes.
With it, we next bound the remainder integral along $\CC_2$.
\proclaim{Lemma 2}
We have
$$\left|\nn\cau_{\CC_2}R_{K}(y-1)\doo\right|\leq H(K)n^{\frac32}2^{-\frac n2},\tag3.7$$
where
$$H(K)=181.7306404 \(\frac{1+\sqrt2}\pi\)^K.$$
\endproclaim
\demo{Proof}
Estimate \thetag{3.2} by the triangle inequality applying the bounds
\thetag{3.5}
of Lemma~1 for the coefficients $c_k$;
use Stirling's formula \thetag{3.4} to eliminate the
factorials. This gives the upper bound
$$\left({11\over10}\,{ne^{-n}\sqrt{2\pi n}\over 2\pi}\right)
\left(M{ {1+\sqrt{2}\over\pi}\over1-{1+\sqrt{2}\over\pi}}\right)
\left({1+\sqrt{2}\over\pi}\right)^k
\left( {
(1+\sqrt{2})e^n\over\sqrt{2}}2^{-n/2}\right)
\left(2\pi\sqrt{2}{3\over4}\right),
$$
with $M=10.96714833$ being the constant appearing in Lemma~1. All
reductions done, this provides the stated bound.
\qed\enddemo
It remains to evaluate the remainder integrals along $\CC_1$.
\proclaim{Lemma 3} For all $n\ge1$, we have the bound
$$\left|{n!\over n^{n-1}}\Cau_{\CC_1} R_{K}(y-1)\,\doo\right|
\le G(K) {1\over n^{K/2}}\tag3.8$$
where
$$G(K)={11\over 10}{2^{K+3}\over\sqrt{2\pi}}{\mu_{K}\Gamma\({K+3\over2}\)}
\qquad\hbox{\sl and}\qquad\mu_{K}=\max_{y\in
\CC_1}\left|{R_{K}(y-1)\over(y-1)^K}\right|\tag3.9$$
\endproclaim
\demo{Proof} Setting $y=1+i\tau$, and
bounding the integral in (3.8), we
find
$$\left|{n!\over n^{n-1}}\cau_{\CC_1} R_{K}(y-1)\,\doo\right|\le
{11\over 10}\,{n\sqrt{2\pi n}\over 2\pi} \mu_{K}J(K),\tag3.10$$
with $\mu_{K}$ defined in (3.9) and
$$\eqalign{J(K)&=\int_{-1}^{+1}|\tau|^{K+2}\,{d\tau\over |1+i\tau|^{n+1}}\cr &<2\int_0^1 \tau^{K+2}\, {d\tau\over(1+\tau^2)^{n/2}}.\cr}\tag3.11$$
Since, in the given range, we have $1+u\ge e^{u/2}$, we find
$$J(K)<2\int_0^\infty \tau^{K+2}e^{-n\tau^2/4}\,d\tau$$
and a change of variable shows that the right hand side
coincides with a gamma function, namely
$$J(K)<2^{K+3}\Gamma\({K+3\over2}\)n^{-(K+3)/2}.\tag3.12$$
Using (3.12) inside (3.10) yields the statement
of the lemma.~\squ\enddemo
\heading 4. Ultimate inequalities and the main theorem \endheading
We are finally in a position to
combine the effective bounds provided by Lemmas 1, 2 and 3
and derive the main result of the paper.
\proclaim{Theorem 2}
With the quantity $\theta\equiv\theta(n)$ being defined by
$${1\over2}e^n=1+{n\over1!}+{n^2\over2!}+\cdots+{n^n\over
n!}\theta,$$
one has, for all integers $n\ge0$,
$$\theta={1\over3}+{4\over135(n+k)},$$
where $k\equiv k(n)$ lies between $8\over45$ and $2\over 21$.
\endproclaim
\demo{Proof} The proof uses the decomposition \thetag{3.1} together with
the estimates derived in the last section. We fix the value
$K=10$. The remainder integral containing $R_K$ is estimated along
$\CC_2$ and $\CC_1$. Then we consider the main terms.
(i). The remainder integral along $\CC_2$
is estimated by Lemma~2.
For $K=10$, we get $H(10)=13.05227701$ so that we find
$$\aligned
\left|{n!\over n^{n-1}}\cau_{\CC_2} R_{10}(y-1)\,\doo\right|\
& < 13.06n^{3/2}2^{-n/2} \cr
& <\ 10^{-7} {1\over n^3} \qquad\hbox{for }n\geq n_0=116.
\endaligned
\tag4.1$$
(Numerical studies show that much better could be done,
but the effect on $n_0$ is marginal.)
(ii).~The remainder integral along $\CC_1$
is estimated by Lemma~3.
This requires estimating the quantity $\mu_{K}$
appearing in the bound (3.8).
The smallness of the $\mu_K$'s is naturally related to the exponential
decay of the coefficients $c_K$ since $\mu_K\approx c_K$.
% and numerical evidence shows that
% $c_K\approx 7^{-K}$. We use again Cauchy's
% formula to prove a weaker exponential bound on the $c_K$'s:
>From Lemma~1, we find with $M=10.96714833$,
$$\mu_{K}\le M\sum_{j>K}{1\over\pi^j}={M\over \pi-1}\({1\over\pi}\)^K,$$
and in particular, for $K=10$:
$$\mu_{10}<0.00005468 \qquad\hbox{so that}\qquad G(10)=56.59398.$$
(From numerical experiments, we expect a slightly better bound
to hold: $\mu_{10}<10^{-7}$---but once more the effect is marginal.)
(iii).~We finally consider the first 10 ($=K$) terms in the expansion
\thetag{3.1} which contribute a polynomial of degree 9 in $1\over n$
to $D(n)$.
Define
$$\aligned D_{10}(n) & = \nn\Cau_{\CC}\sum_{k=0}^{10}c_k(y-1)^k\doo \cr
& = \frac{2}{3}+{\frac {8}{135\,n}}-{\frac
{16}{2835\,n^{2}}}-{\frac{32}{8505\,n^
{3}}}+{\frac {17984}{12629925\,n^{4}}}+{\frac {13159709}{9699782400\,n
^{5}}} \cr
& \ \ -{\frac {977069}{1039262400\,n^{6}}}-{\frac {36669961}{
28291032000\,n^{7}}}+{\frac {117191}{56582064\,n^{8}}}-{\frac {479}{
561330\,n^{9}}} \, .
\endaligned $$
% $$D_{10}(n)=\nn\Cau_{\CC}\sum_{k=0}^{10}c_k(y-1)^k\doo
% $$
% $$=
% \frac{2}{3}+{\frac {8}{135\,n}}-{\frac {16}{2835\,n^{2}}}-{\frac{32}{8505\,n^
% {3}}}+{\frac {17984}{12629925\,n^{4}}}+{\frac {13159709}{9699782400\,n
% ^{5}}}
% $$
% $$-{\frac {977069}{1039262400\,n^{6}}}-{\frac {36669961}{
% 28291032000\,n^{7}}}+{\frac {117191}{56582064\,n^{8}}}-{\frac {479}{
% 561330\,n^{9}}} \, .
% $$
Equation \thetag{3.1} and the bounds found for $K=10$ yield
$$
D_{10}(n)-\Delta(n)\le D(n)\le D_{10}(n)+\Delta(n) \tag{4.2}$$
where
$$\Delta(n)= {10^{-7}\over n^3}+{57\over n^5},$$
under the sole condition that $n\ge n_0=116$.
The two basic inequalities
$$\aligned & D_{10}(n)-\Delta(n) \geq \frac23+\frac 8{135(n+\frac8{45})}
\qquad\text{for }n\geq n_1=24\cr
& D_{10}(n)+\Delta(n) \leq \frac23+\frac 8{135(n+\frac2{21})}
\qquad \text{for }n\geq n_2= 116,
\endaligned$$
are verified by normalizing the involved rational fractions and studying the
variations of the numerator polynomials that are of degrees~8 and~7
respectively. Thus, from~\thetag{4.2}, the main assertion of the theorem is
established for
$$n\geq \max(n_0,n_1,n_2)=116.$$
% $$\aligned &D_{10}(n)\geq \frac23+\frac 8{135(n+\frac8{45})}+\frac{10^{-7}}{n^3}+\frac{G(10)}{n^5}\quad\text{for }n\geq 24\cr
% &D_{10}(n)\leq\frac23+\frac8{135(n+\frac2{21})}-\frac{10^{-7}}{n^3}-\frac{G(10)}{n^5}\quad\text{for }n\geq 106.\endaligned$$
%
To finish the proof,
it suffices to calculate $k(n)$ for $n\leq 115$ by computer and to
verify the inequality in these cases (see Fig.~2 for a display).
\qed\enddemo
{\sl Proof and Computation.}
The symbolic manipulations needed by our proof
were performed with the help of the computer algebra system {Maple}.
Computer algebra intervened at most stages in the construction
of the proof: in performing various expansions like (2.6),(2.8),(2.9),
and in obtaining the various bounds of Sections 3 and 4.
As soon as enough terms have been gathered in
the asymptotic expansion of $Q(n)$, the truth of the conjecture
in its weaker asymptotic form, for ``large enough'' $n$, is immediate.
The difficulty in obtaining a complete proof of Theorem~2 is then twofold:
(i).~the proof of asymptotic estimates should be suitably transformed
in order to yield inequalities valid for large enough $n$;
(ii).~the range of excluded values of $n$ should be small enough that
the remaining cases, here $n<116$, be amenable to exhaustive verification.
The second of these conditions
has necessitated a rather delicate tuning process
that could be done rather painlessly with the help of a few
hours of interaction
with our computer algebra system. A hand carved proof
along our lines, though perhaps conceivable, would have involved a rather
formidable calculational effort.
\topinsert
\vskip 8cm
\special{psfile=rama3.ps hscale=45 vscale=45 hoffset=36}
\vskip 0.3cm
\noindent
{\bf Figure~2.} A plot of the first 120 values of $k(n)$ confirms that
they all lie inside the interval $[{2\over21},{8\over45}]$.
\medskip\noindent\hrule\medskip
\endinsert
\heading 5. Some Conclusions \endheading
It may be of interest, at last, to reflect on the various alternatives
that offer themselves in order to estimate
asymptotically sequences like $Q(n)$ or $D(n)$.
1. {\sl Laplace Method.} The Laplace method for integrals, based on
the integral representation (1.5) was the starting point of earlier approaches.
As Szeg\"o and Watson show, it can be made ``constructive'' (instead of providing
only $O$-bounds) but its operation
becomes then somewhat intricate.
2. {\sl Singularity Analysis.}
This is the method that gave us here the expansion of Theorem~1.
It is based on the fact that the implicitly defined function $y(z)$
has an algebraic singularity of the $\sqrt{\ }$--type, from which the
singularity types of the generating functions associated with $Q(n)$ or
$D(n)$ follow.
The method can also accommodate
constructive bounds on a function's coefficients~\cite{FO90b}.
Consequently it might be applicable to derive Theorem~2,
although, in this case, bounding
$y(z)$ in the appropriate region would probably prove unwieldy.
3. {\sl Darboux's Method.}
Darboux's method also leads to a full asymptotic expansion by a route
very similar to singularity analysis. However it does not have the
capacity to provide bounds since it is intrinsically based on a
non--constructive lemma on Fourier series.
4. {\sl Saddle Point.} This is in essence
the route that we took, after a suitable change of variable.
Its application in the case of implicitly defined functions
and Lagrange series is also to be
traced in Darboux's works, an interesting combinatorial application occurring
in \cite{MM78}. By this method, we were able
to reduce the problem
to the task of finding simple bounds for elementary functions
on circles and line segments. Interestingly enough,
when considering the conformal mapping defined by $y^{(-1)}(z)$,
it appears that the induced contour in the $z$--plane closely
resembles the type of ``Hankel'' contour used in the $z$--plane under the
singularity analysis approach. This establishes a perhaps unexpected
relation between two seemingly unrelated methods---singularity
analysis and saddle point---at least in the context of implicitly
defined functions and Lagrange series.
% \newpage
\Refs
\ref\key Be89
\by B. Berndt
\book Ramanujan's Notebooks, Part II
\publ Springer\publaddr Berlin
\yr 1989
\endref
\ref\key CR92
\by K. Compton and C. Ravishankar
\paper Mean Deadlock Time in a Multiprocessing System
\yr 1992
\jour Preprint
\endref
\ref\key DB81
\by N. G. de Bruijn
\book Asymptotic Methods in Analysis
\publ Dover
\yr 1981
\endref
\ref\key FGT92
\by P. Flajolet, D. Gardy and L. Thimonier
\paper Birthday paradox, coupon collectors, caching algorithms,
and self--organizing search
\jour Discrete Applied Mathematics
\yr 1992
\vol 42
\pages In press
\endref
\ref\key FO90a
\by P. Flajolet and A.M. Odlyzko
\paper Random Mapping Statistics
\jour Lect. Notes in Comp. Sc.
\vol 434
\pages 329--354.
In {\it Advances in Cryptology},
Proceedings of {Eurocrypt'89}, % Houtalen, Belgium, April 1989.
J-J. Quisquater and J. Vandewalle Editors.
\yr 1990
\endref
\ref\key FO90b
\by P. Flajolet and A.M. Odlyzko\paper Singularity Analysis of
Generating Functions\jour SIAM J. Disc. Math.\vol 3\pages 216--240\yr 1990\endref
\ref\key GJ83
\by I.P. Goulden and D.M. Jackson\book Combinatorial Enumeration
\publ J. Wiley\publaddr New York\yr 1983\endref
\ref\key Ha78
\by G. H. Hardy
\book Ramanujan: {T}welve Lectures on Subjects Suggested by his Life
and Work
\publ Chelsea Publishing Company \publaddr New York
\yr 1978
\endref
\ref\key He77\by P. Henrici\book Applied and Computational Complex Analysis
\publ J. Wiley\publaddr New York\yr 1977\endref
\ref\key Kn68\by D.E. Knuth\book The Art of Computer Programming\vol 1\publ
Addison Wesley\publaddr Reading\yr 1968\endref
\ref\key Kn69\by D.E. Knuth\book The Art of Computer Programming\vol 2\publ
Addison Wesley\publaddr Reading\yr 1969\endref
\ref\key Kn73\by D.E. Knuth\book The Art of Computer Programming\vol 3\publ
Addison Wesley\publaddr Reading\yr 1973\endref
\ref\key Kn85\by D.E. Knuth\paper An analysis of optimal caching
\yr 1985\jour J. of Algorithms \pages 181--199\endref
\ref\key KP89
\by D. E. Knuth and B. Pittel
\paper A recurrence related to trees
\yr 1989
\jour Proc. Amer. Math. Soc.
\vol 105
\pages 335--349
\endref
\ref\key KR75
\by D. E. Knuth and G. S. Rao
\paper Activity in an Interleaved Memory
\yr 1975
\jour IEEE Transactions on Computers
\vol C-24
\pages 943--944
\endref
\ref\key KS78
\by D. E. Knuth and A. Sch{\"o}nhage
\paper The expected linearity of a simple equivalence algorithm
\yr 1978
\vol 6
\jour Theoret. Comp. Science
\pages 281--315
\endref
\ref\key MM78\by A. Meir and J.W. Moon\paper
On the altitude of nodes in random trees\yr 1978
\jour Canadian Journal of Mathematics\vol 30\pages 997--1015\endref
\ref\key Ra11
\by S. Ramanujan
\paper Question 294
\jour J. Indian Math. Soc.
\vol 3
\yr 1911
\pages 128
\endref
\ref\key Ra12
\by S. Ramanujan
\paper On question 294
\jour J. Indian Math. Soc.
\vol 4
\yr 1912
\pages 151--152
\endref
\ref\key Ra62
\by S. Ramanujan
\book Collected Papers
\publ Chelsea Publishing Company \publaddr New York
\yr 1962
\endref
\ref\key Sz28\by G. Szeg\H o\paper \"Uber einige von S. Ramanujan gestellte
Aufgaben\jour J. London Math. Soc.\pages 225--232\vol 3\yr 1928\endref
\ref\key VF90
\by J. S. Vitter and P. Flajolet
\paper Analysis of Algorithms and Data Structures
\jour
In Handbook of Theoretical Computer Science. Vol~A: Algorithms and
Complexity (J. van Leeuwen Ed.), Chapter~9
\yr 1990
\pages 431--524
\endref
\ref\key Wa29\by G.N. Watson\paper Theorems Stated by Ramanujan (V): Approximations
Connected with $e^x$\jour Proc. London Math. Soc. (2)\vol 29\pages 293--308
\yr 1929\endref
\endRefs
\enddocument