ON RAMANUJAN’S Q–FUNCTION^{†}

Philippe Flajolet, Peter J. Grabner, Peter Kirschenhofer and Helmut Prodinger

Dedicated to D. E. Knuth, on the occasion of the 30th Anniversary of his first analysis of an algorithm in 1962.

Abstract. This study provides a detailed analysis of a function which Knuth discovered to play a central rôle 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 problems 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 (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.

— August 25, 1993 —

1. Introduction

In the 1911 issue of the Journal of the Indian Mathematical Society, Ramanujan [Ra11] poses the following problem: Show that

(1.1)  \frac{1}{2}e^{n} = 1 + \frac{n}{1!} + \frac{n^{2}}{2!} + ⋯ + \frac{n^{n}}{n!} θ,  where θ lies between \frac{1}{2} and \frac{1}{3}.

A solution was then outlined in [Ra12]. Later in his first letter to Hardy dated January 16, 1913 (see [Ra62, p. xxvi], [Be69, p. 181] and [Ha78]), Ramanujan makes a stronger assertion, namely that

(1.2)  θ = \frac{1}{3} + \frac{4}{135(n + k)}  where k lies between \frac{8}{45} and \frac{2}{21}.

†Research of the four authors was supported by the French Austrian scientific cooperation programme. 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

Typeset by AMS-TEX

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+⋯+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 \frac{1}{2} and the argument supplemented by elementary real estimates readily shows that θ ≡ θ(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 [Be89]) as well as to Entry 6 of Chapter 13 (p. 193–195 of [Be89]). Berndt qualifies the problem as “an ultimately famous problem”. In his partial answer [Ra12] and in the notebooks, Ramanujan provides in essence a way of constructing an asymptotic expansion for θ ≡ θ(n). ¿From his analysis there results that θ(∞) = \frac{1}{3} while we have θ(0) = \frac{1}{2}. This, translated in terms of k ≡ k(n) says that k(∞) = \frac{2}{21} and k(0) = \frac{8}{45}, 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ő in 1928 [Sz28], and almost simultaneously Watson [Wa29] wrote a paper where he proved (1.1) and adds regarding (1.2): “ I shall also give reasons, which seem to me fairly convincing, for 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 [Ra12] and 75 years after Ramanujan’s birth, Knuth conducted his first average–case analysis of an algorithm, namely the analysis of hashing with linear probing (see the footnote on page 529 of [Kn73]). That analysis is given in full in Volume 3 of The Art of Computer Programming [Kn73] and, in Volume 1, Knuth uses it as an illustration of asymptotic analysis techniques [Kn68, p.113]. A key rôle in the analysis is played by a function closely related to θ(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

(1.3)  \begin{aligned}Q(n) & = 1 + \frac{n − 1}{n} + \frac{(n − 1)(n − 2)}{n^{2}} + ⋯ \\ R(n) & = 1 + \frac{n}{n + 1} + \frac{n^{2}}{(n + 1)(n + 2)} + ⋯, \end{aligned}

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

(1.4)  \frac{n^{n}}{n!} Q(n) = \frac{n^{n−1}}{(n − 1)!} + \frac{n^{n−2}}{(n − 2)!} + ⋯ + 1,

which entails

\frac{n^{n}}{n!} Q(n) = \frac{1}{2}e^{n} − θ \frac{n^{n}}{n!}  and  θ(n) = \frac{1}{2}(R(n) − Q(n)).

In this way, Ramanujan’s problem can be rephrased as: “Show that

R(n) − Q(n) = \frac{2}{3} + \frac{8}{135(n + k)}

where k ≡ k(n) lies between \frac{2}{21} and \frac{8}{45}”. 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θ(n).

The approaches followed by Ramanujan himself and later authors all make use of real integral representations derived from

(1.5)  Q(n) = ∫_{0}^{∞} e^{−x}(1 + \frac{x}{n})^{n} dx,

and proceed using the Laplace method for the asymptotic evaluation of integrals [DB81]. ¿From this representation, Q(n) is up to normalization an incomplete gamma function, a _{1}F_{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 [Be89]).

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ős-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: The number of integers less than n with numbers of prime divisors at most k is asymptotically

\frac{x}{log x}[1 + \frac{log log x}{1!} + \frac{(log log x)^{2}}{2!} + ⋯ + \frac{(log log x)^{k}}{k!} ].

Letting k vary with n in the “interesting” region k ≈ 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:

(1) 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 [Kn73] or [FGT92]). For instance, on earth, it takes on average only 24.61658 persons to find two with the same birth date.

(2) 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 \frac{1}{2} \sqrt{\frac{πn}{2}}, as results from the asymptotic analysis of Q(n) (see [Kn73, p. 530] and [VF90, p. 509–511]).

(3) Random mapping statistics involve Q(n) in several places, in relation to their cycle structure. There is a vast literature on this topic, see [Kn69, p. 8] for the basic results, [KP89] for related problems, and [FO90a] for a recent survey of random mapping statistics. The corresponding analyses are also relevant to the study of random number generators [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.

(4) Analysis of Union–Find algorithms under the random spanning tree model essentially depends on Q(n) [KS78].

(5) Analysis of optimum caching [Kn85] and the study of memory conflicts or deadlocks [KR75,CR92] involve the function Q(n).

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.

2. Generating Functions, Asymptotics, and an Integral Representation

An important function in combinatorial analysis is the function y(z) defined implicitly by the equation

(2.1)  y(z) = ze^{y(z)},

with y(z) = z + z^{2} + 3z^{3}/2 + · · ·. By the Lagrange inversion formula, we have^{1}

Proposition 1. The Taylor coefficients of y(z) = ze^{y(z)} and its powers are given by

(2.2)  [z^{n}]y(z) = \frac{n^{n−1}}{n!}  and  [z^{n}]y^{k}(z) = k \frac{n^{n−k−1}}{(n − k)!}.

Furthermore, a generating function of Q(n) is expressible in terms of y(z):

(2.3)  ∑_{n=1}^{∞} Q(n)n^{n−1} \frac{z^{n}}{n!} = log \frac{1}{1 − y(z)} .

The well known expansions (2.2) go back to Legendre and Eisenstein. The companion facts from combinatorics are classical (see [GJ83] or [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ényi and Harris.

1We let [z^{n}]f(z) denote the coefficient of z^{n} in the Taylor expansion of f(z).

Equation (2.3) has already appeared in the literature [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 [Be89,Wa29,Kn68].

Theorem 1. [Ramanujan, Watson, Knuth] The quantities Q(n), R(n) admit full asymptotic expansions in descending powers of \sqrt{n}:

Q(n) ∼ \sqrt{\frac{πn}{2}} − \frac{1}{3} + \frac{1}{12}\sqrt{\frac{π}{2n}} − \frac{4}{135n} + ⋯

R(n) ∼ \sqrt{\frac{πn}{2}} + \frac{1}{3} + \frac{1}{12}\sqrt{\frac{π}{2n}} + \frac{4}{135n} + · · · .

Proof. We sketch here the proof based on singularity analysis (see [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 − ε + \frac{1}{3}ε^{2} − \frac{11}{72}ε^{3} + \frac{43}{540}ε^{4} − ⋯, ε = \sqrt{2 − 2ez},

as z → e^{−1}. This induces a logarithmic singularity for L(z) at z = 1/e,

L(z) = log \frac{1}{ε} + \frac{1}{3}ε − \frac{7}{72}ε^{2} + \frac{133}{3240}ε^{3} + ⋯ = \frac{1}{2} log(1 − ez)^{−1} + · · · .

By singularity analysis [FO90b], the asymptotic equivalent of L(z) transfers to the coefficients, which gives [z^{n}]L(z) ∼ \frac{1}{2}e^{n}n^{−1}, and Q(n) ∼ \sqrt{π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. □

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

∑_{n=1}^{∞} D(n)n^{n−1} \frac{z^{n}}{n!} = log \frac{(1 − y)^{2}}{2(1 − ez)}.

Appeal to Cauchy’s integral formula for coefficients of analytic functions. When applied to (2.3), it gives

(2.4)  D(n) = \frac{n!}{n^{n−1}} \frac{1}{2πi} ∮_{C} log \frac{(1 − y(z))^{2}}{2(1 − ez)} dω  with  dω = \frac{dz}{z^{n+1}} ,

where C is a sufficiently small countour surrounding the origin.

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

Proposition 2. Quantity D(n) = R(n) − Q(n) satisfies (2.5)

D(n) = \frac{n!}{n^{n−1}} \frac{1}{2πi} ∮_{C} log \frac{(1 − y)^{2}}{2(1 − ye^{1−y})} dω with dω = \frac{dz}{z^{n+1}} = (1 − y)e^{ny} \frac{dy}{y^{n+1}} ,

where C is a small contour around the origin in either the z–plane (the first form of dω 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).

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:

(2.6)  \begin{matrix}\frac{n!}{n^{n−1}} [z^{n}](y − 1) = 1, \frac{n!}{n^{n−1}} [z^{n}](y − 1)^{2} = −\frac{2}{n}, \\ \frac{n!}{n^{n−1}} [z^{n}](y − 1)^{3} = −\frac{3}{n} + \frac{6}{n^{2}} , \frac{n!}{n^{n−1}} [z^{n}](y − 1)^{4} = \frac{20}{n^{2}} − \frac{24}{n^{3}} , \\ \frac{n!}{n^{n−1}} [z^{n}](y − 1)^{5} = \frac{15}{n^{2}} − \frac{130}{n^{3}} + \frac{120}{n^{4}}, … \end{matrix}

with n!n^{−n−1}[z^{n}](y − 1)^{k} being O(n^{−⌊k/2⌋}) and comprising ⌈k/2⌉ terms.

If we expand the integrand of (2.5) in powers of (y − 1) and use the first form of dω, dω = dz/z^{n+1}, then through (2.6) we get an asymptotic expansion for D(n):

(2.7)  D(n) ∼ ∑_{k≥1} c_{k} · [z^{n}](y − 1)^{k}

where (δ = y − 1):

(2.8)  \begin{matrix}log \frac{δ^{2}}{2(1 − (1 + δ)e^{−δ})} = ∑_{k≥1} c_{k}δ^{k} \\ = \frac{2}{3}δ − \frac{1}{36}δ^{2} − \frac{1}{810}δ^{3} + \frac{1}{12960}δ^{4} \\ + \frac{1}{68040}δ^{5} + \frac{1}{12247200}δ^{6} − \frac{1}{6123600}δ^{7} − \frac{13}{1175731200}δ^{8} + · · · . \end{matrix}

By (2.6), Eq. (2.7) itself transforms into a standard expansion,

(2.9)  D(n) ∼ ∑_{k≥0} \frac{d_{k}}{n^{k}} ,

whose first few terms are

D(n) ∼ \frac{2}{3} + \frac{8}{135n} − \frac{16}{2835n^{2}} − \frac{32}{8505n^{3}} + \frac{1794}{12629925n^{4}} + · · · .

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 ε) and refinements of it are going to provide the required bounds.

3. Expansions with Effective Error Bounds

The main device employed here follows the outline given in the equations (2.7)– (2.9). We use a terminating form of (2.8) inside our main integral representation,

(3.1)  \frac{n^{n−1}}{n!} D(n) = \frac{1}{2πi} ∮_{C} ( ∑_{k=0}^{K} c_{k}(y − 1)^{k}) dω + \frac{1}{2πi} ∮_{C} R_{K}(y − 1) dω,

where the c_{k} are defined by (2.8) and

(3.2)  R_{K}(y − 1) = log \frac{(1 − y)^{2}}{2(1 − ye^{1−y})} − ∑_{k=1}^{K} c_{k}(y − 1)^{k} = ∑_{k≥K+1} c_{k}(y − 1)^{k}.

The integral with the finite sum in (3.1) is known 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 second form of dω, namely dω = (1 − y)e^{ny}dy/y^{n+1} together with a contour in the y–plane whose choice is dictated by a 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 C = C_{1} ∪ C_{2} where

(3.3)  C_{1} = \{1 + iτ / − 1 ≤ τ ≤ 1\} and C_{2} = \{y / |y| = \sqrt{2}, ℜ(y) ≤ 1\}.

Our proof, that will eventually fix K = 10, consists of two simple phases.

(a) The integral of the remainder term along C_{2} is small since there y^{−n} = O(2^{−n/2}); in addition, it can be effectively bounded.

(b) Along C_{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.

We thus proceed with this programme, starting with estimates of the c_{k} coefficients, continuing with the estimates along C_{2} then C_{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 ≥ 1,

(3.4)  n! < \frac{11}{10}n^{n}e^{−n}\sqrt{2πn}.

Lemma 1. For all k ≥ 1, we have

(3.5)  |c_{k}| < \frac{10.96714833}{π^{k}}.

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

Figure 1. The transform by f(z) of the square of side 2π centered at the origin together with a blow up of the picture near the origin (lower right).

by means of Cauchy’s formula:

(3.6)  c_{k} = \frac{1}{2πi} ∮_{Q} log f(z)\frac{dz}{z^{k+1}} ,

where Q is any small enough simple contour encircling the origin. We propose to take here as contour Q the boundary of the square |ℜz| ≤ π, |ℑz| ≤ π.

First, elementary computations show that there are no zeros nor poles of f(z) within Q. The graph of Figure 1 which represents the image of Q by f(z) confirms this via the principle of the argument since f(Q) has winding number 0 with respect to the origin. Thus log f(z) is analytic in and on Q and the Cauchy integral (3.6) for c_{k} can be evaluated by taking Q as the integration contour.

By considering the four sides of the square |ℜz| ≤ π, |ℑz| ≤ π and using trivial estimates we obtain:

\frac{π^{2}}{2(1 + (2π + 1)e^{π})} ≤ |f(z)| ≤ \frac{π^{2}}{1 − (π + 1)e^{−π}} .

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 ℑ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 ℜz = π, 0 ≤ ℑz ≤ π, −π ≤ ℜz ≤ π, ℑz = π and ℜz = −π, 0 ≤ ℑz ≤ π, we find that g(z) does not enter the third quadrant. Thus we have −\frac{π}{2} < arg g(z) < π. On the other hand we have 0 ≤ arg z^{2} ≤ 2π. Combining the two bounds yields

| arg f(z)| ≤ \frac{5}{2}π.

Thus we obtain

|log f(z)| ≤ (log^{2} \frac{π^{2}}{2((2π + 1)e^{π} + 1)} + \frac{25}{4}π^{2})^{\frac{1}{2}} = 8.613578 ….

Bounding the integral (3.6) trivially, we arrive at

|c_{k}| ≤ \frac{1}{2π} (\frac{8.613578}{π^{k+1}}) (8π),

which is equivalent to (3.5). □

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 C_{2}.

Lemma 2. We have

(3.7)  |\frac{n!}{n^{n−1}} \frac{1}{2πi} ∫_{C_{2}} R_{K}(y − 1)dω| ≤ H(K)n^{\frac{3}{2}} 2^{− \frac{n}{2}} ,

where

H(K) = 181.7306404 (\frac{1 + \sqrt{2}}{π})^{K} .

Proof. Estimate (3.2) by the triangle inequality applying the bounds (3.5) of Lemma 1 for the coefficients c_{k}; use Stirling’s formula (3.4) to eliminate the factorials. This gives the upper bound

(\frac{11}{10} \frac{ne^{−n}\sqrt{2πn}}{2π}) (M \frac{\frac{1+\sqrt{2}}{π}}{1 − \frac{1+\sqrt{2}}{π}} ) (\frac{1 + \sqrt{2}}{π})^{k} (\frac{(1 + \sqrt{2})e^{n}}{\sqrt{2}} 2^{−n/2}) (2π\sqrt{2}\frac{3}{4}) ,

with M = 10.96714833 being the constant appearing in Lemma 1. All reductions done, this provides the stated bound. □

It remains to evaluate the remainder integrals along C_{1}.

Lemma 3. For all n ≥ 1, we have the bound

(3.8)  |\frac{n!}{n^{n−1}} \frac{1}{2πi} ∮_{C_{1}} R_{K}(y − 1) dω| ≤ G(K)\frac{1}{n^{K/2}}

where

(3.9)  G(K) = \frac{11}{10} \frac{2^{K+3}}{\sqrt{2π}} μ_{K}Γ (\frac{K + 3}{2})  and  μ_{K} = max_{y∈C_{1}} |\frac{R_{K}(y − 1)}{(y − 1)^{K}} |

Proof. Setting y = 1 + iτ, and bounding the integral in (3.8), we find

(3.10)  |\frac{n!}{n^{n−1}} \frac{1}{2πi} ∫_{C_{1}} R_{K}(y − 1) dω| ≤ \frac{11}{10} \frac{n\sqrt{2πn}}{2π}μ_{K}J(K),

with μ_{K} defined in (3.9) and

(3.11)  \begin{aligned}J(K) & = ∫_{−1}^{+1} |τ|^{K+2} \frac{dτ}{|1 + iτ|^{n+1}} \\ & < 2 ∫_{0}^{1} τ^{K+2} \frac{dτ}{(1 + τ^{2})^{n/2}} . \end{aligned}

Since, in the given range, we have 1 + u ≥ e^{u/2}, we find

J(K) < 2 ∫_{0}^{∞} τ^{K+2}e^{−nτ^{2}/4} dτ

and a change of variable shows that the right hand side coincides with a gamma function, namely

(3.12)  J(K) < 2^{K+3}Γ (\frac{K + 3}{2}) n^{−(K+3)/2}.

Using (3.12) inside (3.10) yields the statement of the lemma. □

4. Ultimate inequalities and the main theorem

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.

Theorem 2. With the quantity θ ≡ θ(n) being defined by

\frac{1}{2}e^{n} = 1 + \frac{n}{1!} + \frac{n^{2}}{2!} + ⋯ + \frac{n^{n}}{n!} θ,

one has, for all integers n ≥ 0,

θ = \frac{1}{3} + \frac{4}{135(n + k)},

where k ≡ k(n) lies between \frac{8}{45} and \frac{2}{21}.

Proof. The proof uses the decomposition (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 C_{2} and C_{1}. Then we consider the main terms.

(i). The remainder integral along C_{2} is estimated by Lemma 2. For K = 10, we get H(10) = 13.05227701 so that we find

(4.1)  \begin{aligned}|\frac{n!}{n^{n−1}} \frac{1}{2πi} ∫_{C_{2}} R_{10}(y − 1) dω| & < 13.06n^{3/2}2^{−n/2} \\ & < 10^{−7} \frac{1}{n^{3}}  for n ≥ n_{0} = 116. \end{aligned}

(Numerical studies show that much better could be done, but the effect on n_{0} is marginal.)

(ii). The remainder integral along C_{1} is estimated by Lemma 3. This requires estimating the quantity μ_{K} appearing in the bound (3.8). The smallness of the μ_{K}’s is naturally related to the exponential decay of the coefficients c_{K} since μ_{K} ≈ c_{K}.

¿From Lemma 1, we find with M = 10.96714833,

μ_{K} ≤ M ∑_{j>K} \frac{1}{π^{j}} = \frac{M}{π − 1} (\frac{1}{π} )^{K} ,

and in particular, for K = 10:

μ_{10} < 0.00005468  so that  G(10) = 56.59398.

(From numerical experiments, we expect a slightly better bound to hold: μ_{10} < 10^{−7}—but once more the effect is marginal.)

(iii). We finally consider the first 10 (= K) terms in the expansion (3.1) which contribute a polynomial of degree 9 in \frac{1}{n} to D(n). Define

D_{10}(n) = \frac{n!}{n^{n−1}} \frac{1}{2πi} ∮_{C} ∑_{k=0}^{10} c_{k}(y − 1)^{k}dω

= \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 (3.1) and the bounds found for K = 10 yield

(4.2)  D_{10}(n) − Δ(n) ≤ D(n) ≤ D_{10}(n) + Δ(n)

where

Δ(n) = \frac{10^{−7}}{n^{3}} + \frac{57}{n^{5}} ,

under the sole condition that n ≥ n_{0} = 116.

The two basic inequalities

D_{10}(n) − Δ(n) ≥ \frac{2}{3} + \frac{8}{135(n + \frac{8}{45})} for n ≥ n_{1} = 24

D_{10}(n) + Δ(n) ≤ \frac{2}{3} + \frac{8}{135(n + \frac{2}{21})} for n ≥ n_{2} = 116,

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 (4.2), the main assertion of the theorem is established for

n ≥ max(n_{0}, n_{1}, n_{2}) = 116.

To finish the proof, it suffices to calculate k(n) for n ≤ 115 by computer and to verify the inequality in these cases (see Fig. 2 for a display). □

Figure 2. A plot of the first 120 values of k(n) confirms that they all lie inside the interval [\frac{2}{21}, \frac{8}{45}].

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.

5. Some Conclusions

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. Laplace Method. The Laplace method for integrals, based on the integral representation (1.5) was the starting point of earlier approaches. As Szegö and Watson show, it can be made “constructive” (instead of providing only O-bounds) but its operation becomes then somewhat intricate.

2. 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 √ –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 [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. 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. 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 [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.

References

[Be89] B. Berndt, Ramanujan’s Notebooks, Part II, Springer, Berlin, 1989.

[CR92] K. Compton and C. Ravishankar, Mean Deadlock Time in a Multiprocessing System, Preprint (1992).

[DB81] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981.

[FGT92] P. Flajolet, D. Gardy and L. Thimonier, Birthday paradox, coupon collectors, caching algorithms, and self–organizing search, Discrete Applied Mathematics 42 (1992), In press.

[FO90a] P. Flajolet and A.M. Odlyzko, Random Mapping Statistics, Lect. Notes in Comp. Sc. 434 (1990), 329–354. In Advances in Cryptology, Proceedings of Eurocrypt’89, J-J. Quisquater and J. Vandewalle Editors..

[FO90b] P. Flajolet and A.M. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216–240.

[GJ83] I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, J. Wiley, New York, 1983.

[Ha78] G. H. Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by his Life and Work, Chelsea Publishing Company, New York, 1978.

[He77] P. Henrici, Applied and Computational Complex Analysis, J. Wiley, New York, 1977.

[Kn68] D.E. Knuth, The Art of Computer Programming, vol. 1, Addison Wesley, Reading, 1968.

[Kn69] D.E. Knuth, The Art of Computer Programming, vol. 2, Addison Wesley, Reading, 1969.

[Kn73] D.E. Knuth, The Art of Computer Programming, vol. 3, Addison Wesley, Reading, 1973.

[Kn85] D.E. Knuth, An analysis of optimal caching, J. of Algorithms (1985), 181–199.

[KP89] D. E. Knuth and B. Pittel, A recurrence related to trees, Proc. Amer. Math. Soc. 105 (1989), 335–349.

[KR75] D. E. Knuth and G. S. Rao, Activity in an Interleaved Memory, IEEE Transactions on Computers C-24 (1975), 943–944.

[KS78] D. E. Knuth and A. Schönhage, The expected linearity of a simple equivalence algorithm, Theoret. Comp. Science 6 (1978), 281–315.

[MM78] A. Meir and J.W. Moon, On the altitude of nodes in random trees, Canadian Journal of Mathematics 30 (1978), 997–1015.

[Ra11] S. Ramanujan, Question 294, J. Indian Math. Soc. 3 (1911), 128.

[Ra12] S. Ramanujan, On question 294, J. Indian Math. Soc. 4 (1912), 151–152.

[Ra62] S. Ramanujan, Collected Papers, Chelsea Publishing Company, New York, 1962.

[Sz28] G. Szegő, Über einige von S. Ramanujan gestellte Aufgaben, J. London Math. Soc. 3 (1928), 225–232.

[VF90] J. S. Vitter and P. Flajolet, Analysis of Algorithms and Data Structures, In Handbook of Theoretical Computer Science. Vol A: Algorithms and Complexity (J. van Leeuwen Ed.), Chapter 9 (1990), 431–524.

[Wa29] G.N. Watson, Theorems Stated by Ramanujan (V): Approximations Connected with e^{x}, Proc. London Math. Soc. (2) 29 (1929), 293–308.

P. Flajolet

Algorithms Project

INRIA, Rocquencourt

78153 Le Chesnay (France)

P.J. Grabner

Technische Universität Graz Steyrergasse 30 A–8010 Graz (Austria)

P. Kirschenhofer & H. Prodinger Technische Universität Wien Wiedner Hauptstraße 8–10 A–1040 Vienna (Austria)