Some Analytic Techniques for the Investigation of the Asymptotic Behaviour of Tree Parameters

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna Wiedner Hauptstraße 8–10 A–1040, Vienna, Austria

Written for the Proceedings of the Summerschool in Ile de Ré 1983 (in French)

Retyped 1991

Translated into English January 1992

1. Introduction

The structure of a tree is one of the most common data structures in Computer Science. There exist many algorithms for the manipulation of trees. The analysis of these algorithms in the sense of Knuth leads often to combinatorial problems of the enumeration of configurations; the following step consists of the asymptotic analysis of these numbers. See e.g. [4], [15], [16].

The study of Flajolet and Odlyzko [7] is a paradigm for a slightly different point of view: Instead of extracting the coefficients of generating functions and approximating them by methods of real analysis, the singularities of the generating functions are studied. More precisely, one tries to establish the local behaviour of the generating functions around their singularities next to the origin. After that, some translation lemmas allow to translate this behaviour into the asymptotic behaviour of the (Taylor-)coefficients of the generating function in question. For instance, if f(z) = ∑_{n≥0} f_{n}z^{n} has its singularity next to the origin at 1, with

f(z) ∼ A − B\sqrt{1 − z} + …,

then one concludes that

[z^{n}] f(z) := f_{n} ∼ \frac{B}{2\sqrt{π}} n^{−3/2}.

Similarily if

f(z) ∼ −A log(1 − z) + …,

then

[z^{n}]f(z) ∼ \frac{A}{n}, etc.

Also, the more terms we know from the local behaviour of the generating function, the more terms we know from the asymptotic behaviour of the (Taylor-)coefficients.

This translation is a rather automatic process. The principle problem is thus to find the local behaviour around the (dominant) singularities. In a lot of cases one can use the Mellin transform, a very popular method within the french school of the analysis of algorithms.

The main interest of this paper is to explain this general strategy in 3 particular cases: the problem of register allocation for the evaluation of arithmetic expressions; then the height of leaves in planted plane trees. The third problem is the asymptotic study of a certain expression (that is similar to one occurring in the register problem); this value is of interest in the analysis of a particular sorting algorithm (see [6], [21]).

Before we engage ourselves into technical problems, we would like to formulate some fundamental concepts:

The family B of binary trees might be defined recursively by the (symbolic) equation

which means that a binary tree is either an external node (“leaf”) or built by a root and 2 binary trees (the left and right subtree). Let B(z) = ∑_{n≥0} b_{n}z^{n} denote the generating function where b_{n} is the number of binary trees of size n (the size is measured in termes of internal nodes); one can see immediately that

B(z) = 1 + z (B(z))^{2} ,

and thus

B(z) = \frac{1 − \sqrt{1 − 4z}}{2z} and b_{n} = \frac{1}{n + 1}\binom{2n}{n}.

The numbers b_{n} are Catalan numbers.

In an analogous way, the family P of planted plane trees is defined by

form which one deduces the generating function P (z) = ∑_{n≥1} t_{n}z^{n} of planted plane trees:

P (z) = \frac{z}{1 − P (z)} and thus P (z) = \frac{1 − \sqrt{1 − 4z}}{2} and t_{n} = \frac{1}{n}\binom{2n − 2}{n − 1}.

In these 2 cases, the above mentioned singularity is z = \frac{1}{4}, and

B(z) ∼ 2 − 2\sqrt{1 − 4z}, thus b_{n} ∼ \frac{1}{\sqrt{π}} 4^{n}n^{−3/2}

or

P (z) ∼ \frac{1}{2} − \frac{1}{2}\sqrt{1 − 4z}, thus t_{n} ∼ \frac{1}{\sqrt{π}} 4^{n−1}n^{−3/2}.

2. The average number of registers to evaluate a binary tree of size n

Before we start the discussion, let’s cite the references on this subject: [4], [5], [8], [11], [17], [19]. We won’t go into a description of the Computer Science problem. For this we advise the gentle reader to consult the thesis of P. Flajolet [4].

The function “number of registers” reg is given recursively by

reg(□) = 0
reg ( ) = \{ \begin{matrix}max\{reg(t_{1}), reg(t_{2})\} & if reg(t_{1}) ≠ reg(t_{2}) \\ 1 + reg(t_{1}) & otherwise. \end{matrix}

The problem is the evaluation of R_{n}, the average value of the function reg, based on the set of binary trees of size n. We have

R_{n} = \frac{1}{b_{n}} · [z^{n}]E(z),

with

E(z) = ∑_{n≥0} z^{n} ∑_{t of size n} reg(t).

Let R_{p} be the family of trees t with reg(t) = p. From the definition of reg we easily see that

Let S_{p} be the family of trees t with reg(t) ≥ p, that means

S_{p} = R_{p} + R_{p+1} + ….

We can write

∑_{j<p−1} R_{j} = B \ S_{p−1}.

We obtain a recursion for the families S_{p} in a very similar fashion:

The functions S_{p}(z) are defined by

S_{p}(z) := ∑_{n≥0} z^{n} ∑_{t of size n, reg(t)≥p} 1.

It is clear that

E(z) = ∑_{p≥1} S_{p}(z).

The functions S_{p}(z) may be described by the immediate recursions

S_{0} = B; S_{p} = zS_{p−1}^{2} + 2zS_{p} (B − S_{p−1}) .

Summerschool Ile de Ré (English version) 4 It is convenient to define ε := \sqrt{1 − 4z} and z = u/(1 + u)^{2}. Thus

S_{p} = \frac{zS_{p−1}^{2}}{1 − 2zB + 2zS_{p−1}} ,

or

\frac{1}{S_{p}} = \frac{ε}{zS_{p−1}^{2}} + \frac{2}{S_{p−1}} .

This finally gives us

\begin{aligned}1 + \frac{ε}{z} \frac{1}{S_{p}} & = 1 + \frac{ε^{2}}{z^{2}S_{p−1}^{2}} + \frac{2ε}{z} \frac{1}{S_{p−1}} = (1 + \frac{ε}{z} · \frac{1}{S_{p−1}} )^{2} \\ & = ⋯ = (1 + \frac{ε}{z} · \frac{1}{S_{0}} )^{2^{p}} . \end{aligned}

From this we derive the equation

S_{p} = \frac{ε}{z} ((1 + \frac{ε}{zB} )^{2^{p}} − 1)^{−1} .

Now we see at once that

\frac{ε}{z} = \frac{1 − u^{2}}{u} , and 1 + \frac{ε}{zB} = \frac{1}{u},

so that

S_{p} = \frac{1 − u^{2}}{u} \frac{1}{u^{−2^{p}} − 1} = \frac{1 − u^{2}}{u} \frac{u^{2^{p}}}{1 − u^{2^{p}}} .

For the function E(z) we have therefore the following expression

E(z) = \frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{2^{p}}}{1 − u^{2^{p}}}

= \frac{1 − u^{2}}{u} ∑_{p≥1} ∑_{λ≥1} u^{λ2^{p}}

= \frac{1 − u^{2}}{u} ∑_{n≥2} v_{2}(n)u^{n},

where v_{2}(n) is the exponent of 2 in the prime number decomposition of n:

v_{2}(n) = ∑_{n=λ2^{p}, λ,p≥1} 1.

If we write in a unique way n = 2^{m}(1 + 2i), (m ≥ 1, i ≥ 0), we have

v_{2}(n) = ∑_{p=1}^{m} 1 = m.

The quantity v_{2}(n) is often called “dyadic valuation”, for obvious reasons. As it was announced in the Introduction, we will finally show that in a neighbourhood of z = \frac{1}{4} (which means u = 1):

E(z) ∼ 2ε log_{2} ε + Aε + 4 ∑_{k≠0} c_{k}ε^{1−χ_{k}} + …,

with

A = 3 − 2 log_{2} 2π + \frac{2γ}{log 2}, (γ is Euler’s constant)

and

χ_{k} = \frac{2kπi}{log 2} and c_{k} = \frac{1}{log 2}Γ(χ_{k})ζ(χ_{k})

(Γ is Euler’s gamma function, ζ is Riemann’s zeta funtion).

Let us mention the following expansion ([10])

[z^{n}] log(1 − z)(1 − z)^{α} ∼ \frac{−n^{−α−1} log n}{Γ(−α)} + n^{−α−1} \frac{Γ(−α)}{(Γ(−α))^{2}} ,

which gives us as a special instance

[z^{n}] ε log ε ∼ \frac{1}{2}4^{n}n^{−3/2} (\frac{log n}{2\sqrt{π}} + \frac{γ + 2 log 2 − 2}{2\sqrt{π}}) .

We will also use the result

[z^{n}] ε^{1−χ_{k}} ∼ 4^{n}n^{(χ_{k}−3)/2}/Γ (\frac{χ_{k} − 1}{2}) .

We observe that we can simplify the expression

c_{k}/Γ (\frac{χ_{k} − 1}{2}) = \frac{ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1)}{4\sqrt{π} log 2};

for this we use the duplication formula of Legendre-Gauss (see e.g. [2])

Γ (\frac{z}{2}) Γ (\frac{z + 1}{2}) = \sqrt{π}2^{1−z}Γ(z).

Finally, if we collect everything, we find that

[z^{n}] E(z) ∼ \frac{4^{n}n^{−3/2}}{2\sqrt{π} log 2} (log n + γ + 2 log 2 − 2)

− A\frac{4^{n}}{2\sqrt{π}} n^{−3/2} + ∑_{k≠0} \frac{4^{n}n^{(χ_{k}−3)/2}ζ(χ_{k})Γ(χ_{k}/2)(χ_{k} − 1)}{\sqrt{π} log 2}.

If we take into consideration that

b_{n} ∼ \frac{4^{n}}{\sqrt{π}} n^{−3/2}  and  n^{χ_{k}/2} = ε^{log_{4} n·2kπi},

we obtain Theorem 1. The average number R_{n} of registers to evaluate a binary tree of size n verifies

R_{n} = log_{4} n + D(log_{4} n) + o(1),

where D(x) is a continuous periodic function of period 1; this function can be expanded in a Fourier series as

D(x) = ∑_{k∈ℤ} d_{k}e^{2kπix},

with

d_{0} = \frac{1}{2} − \frac{γ}{2 log 2} − \frac{1}{log 2} + log_{2} π

and

d_{k} = \frac{1}{log 2}ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1), k ≠ 0, χ_{k} = \frac{2kπi}{log 2}.

The remainder of this section ist devoted to the study of the expansion of the function E(z).

To study E(z) for z → \frac{1}{4}, i.e. for u → 1, we set u = e^{−t} and consider E(z) for t → 0. We easily obtain that

\frac{1 − u^{2}}{u} ∼ 2t + ….

Let us turn to the second factor of E(z), which we denote by V (t); the Mellin transform of V (t) is denoted by V^{∗}(s):

V (t) = ∑_{k≥1} v_{2}(k)e^{−kt}; V^{∗}(s) = ∫_{0}^{∞} x^{s−1}V (x)dx

V^{∗}(s) = ∫_{0}^{∞} x^{s−1} ∑_{k≥1} v_{2}(k)e^{−kx}dx

= ∑_{k≥1} v_{2}(k)k^{−s} ∫_{0}^{∞} x^{s−1}e^{−x}dx

We have

∑_{k≥1} v_{2}(k)k^{−s} = 2^{−s} ∑_{k≥1} v_{2}(2k)k^{−s} = 2^{−s} ∑_{k≥1} [1 + v_{2}(k)]k^{−s},

and thus

V^{∗}(s) = \frac{Γ(s)ζ(s)}{2^{s} − 1}.

The Mellin inversion formula gives us

V (t) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞}V^{∗}(s)t^{−s}ds.

We can shift the line of integration to the left, provided we take the residues of the integrand V^{∗}(s)t^{−s} into account. There are poles at s = 1 (originating from the Riemann ζ- function) , at s = 0, −1, −2, … (coming from the function Γ) and at s = χ_{k}, k ∈ ℤ (from (2^{s} − 1)^{−1}). We use the classical expansions to get

V (t) ∼ \frac{1}{t} + \frac{1}{2} log_{2} t − \frac{1}{2} log_{2} 2π + \frac{1}{4} + \frac{γ}{2 log 2}

+ \frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k})t^{−χ_{k}} + …

which gives us the announcedc formula for E(z), after having multiplied the last 2 expansions and noting that

t ∼ 2ε + ….

3. A similar problem: odd-even merge

In the analysis of a sorting algorithm (odd-even merge) one has to consider the quantity

B_{n} = ∑_{k≥1} \begin{matrix}( & {2n \atop n−k} & ) \\ ( & {2n \atop n} & ) \end{matrix}(2F (k) + k),

representing the number of exchanges in the odd-even merge of 2n elements. In this equation,

F (k) = ∑_{0≤j<k} f(j)

and f(j) is the number of digits “1” in the Gray code representation of j (see [6], [21]). Below we see the first few numbers in this representation:

0  0  1100  8
1  1  1101  9
11  2  1111 10
10  3  1110 11
110  4  1010 12
111  5  1011 13
101  6  1001 14
100  7  1000 15
11000 16

The numbers

ϑ(j) := f(j) − f(j − 1)

equal ±1: if k is of the form k = 2^{m}(4i + 1), ϑ(k) = 1; if k is of the form k = 2^{m}(4i + 3), ϑ(k) = −1. We might recognize a great similarity between ϑ(k) and Summerschool Ile de Ré (English version) 8 v_{2}(k) from Section 2. The Dirichlet generating function of the sequence ϑ(k) is

∑_{k≥1} ϑ(k)k^{−s} = ∑_{m≥0} ∑_{i≥0} 2^{−ms}(4i + 1)^{−s} − ∑_{m≥0} ∑_{i≥0} 2^{−ms}(4i + 3)^{−s}

= \frac{1}{1 − 2^{−s}} · \frac{1}{4^{s}} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) ,

where the Hurwitz ζ(s, a)-function is defined by

ζ(s, a) = ∑_{n≥0}(n + a)^{−s} for ℜ(s) > 1.

We can write

B_{n} = \frac{n}{2} + \frac{2}{\binom{2n}{n}}C_{n},

with

C_{n} = ∑_{k≥1} F (k)\binom{2n}{n − k}.

We want to find an analogous function to E(z) (Section 2). Thus we write

C_{n} = ∑_{k≥1} F (k) [u^{n−k}] (1 + u)^{2n}

= [u^{n}] ∑_{k≥1} F (k)u^{k}(1 + u)^{2n}

= [u^{n}] ∑_{k≥1} ∑_{0≤j<k} f(j) u^{k}(1 + u)^{2n}

= [u^{n}] ∑_{j≥0} f(j)u^{j} \frac{u}{1 − u}(1 + u)^{2n}

= [u^{n}] ∑_{j≥0} ∑_{0≤i≤j} ϑ(i)u^{j} \frac{u}{1 − u}(1 + u)^{2n}

= [u^{n}] ∑_{i≥0} ϑ(i)u^{i} \frac{u}{(1 − u)^{2}} (1 + u)^{2n}.

In general, if we have a series Ψ(z), and if we set z = u/(1 + u)^{2}, we have by Cauchy’s theorem

[z^{n}] Ψ(z) = \frac{1}{2πi} ∮ \frac{dz}{z^{n+1}} Ψ(z)

= \frac{1}{2πi} ∮ \frac{du(1 − u)}{(1 + u)^{3}} \frac{(1 + u)^{2n+2}}{u^{n+1}} Ψ(\frac{u}{(1 + u)^{2}} )

= [u^{n}] (1 − u)(1 + u)^{2n−1}Ψ(\frac{u}{(1 + u)^{2}} ).

Thus we can write

C_{n} = [u^{n}] \frac{u(1 + u)}{(1 − u)^{3}} ∑_{i≥1} ϑ(i)u^{i}.

The function appearing in the right hand side of this equation is the analogue of E(z) of Section 2. We easily find that

\frac{u(1 + u)}{(1 − u)^{3}} ∼ \frac{2}{t^{3}} + ….

If we set

V (t) = ∑_{k≥1} ϑ(k)e^{−kt},

then we have

V^{∗}(s) = Γ(s) · \frac{1}{2^{s}} · \frac{1}{2^{s} − 1} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) .

As a consequence we find

V (t) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞}Γ(s) · \frac{1}{2^{s}} · \frac{1}{2^{s} − 1} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) t^{−s}dt.

The difference of the Hurwitz ζ-functions is an entire function; the integrand has poles at s = χ_{k} and s = 0, −1, −2, …. We have (see [22])

ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4}) ∼ \frac{1}{2} + s (2 log Γ(\frac{1}{4}) − \frac{1}{2} log 2 − log π) + …

for s → 0. Also,

Γ(s) ∼ \frac{1}{s} − γ + …

\frac{1}{2^{s} − 1} ∼ \frac{1}{log 2} · \frac{1}{s} − \frac{1}{2} + …

(2t)^{−s} ∼ 1 − s · log(2t) + …

which gives us the residue at s = 0

−\frac{5}{4} − \frac{γ}{2 log 2} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π − \frac{1}{2} log_{2} t.

The residue at s = χ_{k} for k ≠ 0 is simply

\frac{1}{log 2}Γ(χ_{k}) (ζ(χ_{k}, \frac{1}{4}) − ζ(χ_{k}, \frac{3}{4})) t^{−χ_{k}}.

Summerschool Ile de Ré (English version) 10 We can simplify, because

ζ(χ_{k}, \frac{3}{4}) = −ζ(χ_{k}, \frac{1}{4}).

Thus we obtain

C_{n} ∼ [z^{n}] \frac{2}{t^{3}} ( − \frac{1}{2} log_{2} t − \frac{5}{4} − \frac{γ}{2 log 2} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π

+ \frac{2}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})t^{−χ_{k}}),

where, with t ∼ 2ε

C_{n} ∼ [z^{n}] ( − \frac{1}{8}ε^{−3} log_{2} ε − ε^{3}(\frac{7}{16} + \frac{γ}{8 log 2} − \frac{1}{2} log_{2} Γ(\frac{1}{4}) + \frac{1}{4} log_{2} π)

+ \frac{1}{2 log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})ε^{−3−χ_{k}}).

We find, as in Section 2,

[z^{n}] ε^{3} log ε ∼ \frac{4^{n}\sqrt{n}}{\sqrt{π}}( − log n + (2 − γ − 2 log 2)),

[z^{n}] ε^{−3} ∼ \frac{2 · 4^{n}\sqrt{n}}{\sqrt{π}},

[z^{n}] ε^{−3−χ_{k}} ∼ 4^{n} \frac{n^{(1+χ_{k})/2}}{Γ (\frac{3+χ_{k}}{2} )} .

By regrouping the preceeding results we obtain

C_{n} ∼ \frac{4^{n}\sqrt{n}}{\sqrt{π}} log n · \frac{1}{8 log 2}

+ \frac{4^{n}\sqrt{n}}{\sqrt{π}} (−\frac{1}{4 log 2} − \frac{γ}{8 log 2} − \frac{5}{8} + log_{2} Γ(\frac{1}{4}) − \frac{1}{2} log_{2} π)

+ \frac{1}{2}4^{n}\sqrt{n}\frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})\frac{n^{χ_{k}/2}}{Γ (\frac{3+χ_{k}}{2} )}.

We have by the duplication formula

Γ(χ_{k})/Γ (\frac{3 + χ_{k}}{2} ) = \frac{1}{1 + χ_{k}} \frac{1}{\sqrt{π}} Γ (\frac{χ_{k}}{2} ) .

With

\binom{2n}{n} ∼ \frac{4^{n}n^{−1/2}}{\sqrt{π}}

we find

\frac{D_{n}}{\binom{2n}{n}} · \frac{1}{n} ∼ \frac{1}{8} log_{2} n

− \frac{1}{4 log 2} − \frac{γ}{8 log 2} − \frac{5}{8} + log_{2} Γ(\frac{1}{4}) − \frac{1}{2} log_{2} π

+ \frac{1}{2 log 2} ∑_{k≠0} ζ(χ_{k}, \frac{1}{4})\frac{Γ(χ_{k}/2)}{1 + χ_{k}}n^{χ_{k}/2}.

Finally we have obtained the

Theorem 2. The average number of exchanges in the odd-even merge of 2n elements verifies

B_{n} ∼ \frac{1}{4}n log_{2} n + nB( log_{4} n),

where B(x) is a continuous periodic function of period 1; this function can be expanded as a Fourier series

B(x) = ∑_{k∈ℤ} b_{k}e^{2kπix},

with

b_{0} = −\frac{1}{2 log 2} − \frac{γ}{4 log 2} − \frac{3}{4} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π

and for k ≠ 0

b_{k} = \frac{1}{log 2}ζ(χ_{k}, \frac{1}{4})\frac{Γ(χ_{k}/2)}{1 + χ_{k}}.

4. The height of leaves in planted plane trees

We can understand the problem of this section most easily by considering the following example of a planted plane tree:

This tree has 4 leaves of height (from left to right) 3, 3, 4, 2. We remark that the height of the tree is given by the height of the highest leaf We imagine now that the leaves are ordered with respect to their heights. In our example, the sequence of heights of leaves is 4, 3, 3, 2. Let us remark that there might be more leaves with the same height. To simplify the computations, we complete this sequence by an infinity of zeroes. Now it makes sense to speak about the d-th highest leaf for each d, even if the tree has less than d leaves.

Now we consider h_{n}^{(d)}, the average height of the d-th highest leaf where we remark again that h_{n}^{(1)} is simply the average height of a tree of size n.

Some technical lemmas have appeared already in several papers, see [1], [12], [13], [14], [20].

Lemma 1. Let F (z, y) be the generating function where [z^{n}y^{m}] F is the number of trees of size n with m leaves (the tree ∘ has zero leaves); we have for each p ≥ 0

F^{p}(z, y) = z^{p} + p ∑_{0≤λ<n} z^{n}y^{n−λ} \frac{1}{n}\binom{n}{λ}\binom{n − p − 1}{λ − p}.

Idea of proof. (See [12]) We introduce G(z, y), the analogous quantity, where ∘ has a leaf; translating the symbolic equation for the family of planted plane trees as usual we obtain

G(z, y) = z(y + ∑_{r≥1} G^{r}(z, y)) = (1 − z(1 − y))P (\frac{zy}{(1 − z(1 − y))^{2}} ) .

We use the classical expansion

P^{m}(z) = ∑_{k≥0} [\binom{2k + m − 1}{k} − \binom{2k + m − 1}{k − 1}] z^{k+m}.

After this we use the binomial theorem 3 times and use the identity

∑_{k≥0} \binom{r}{k}\binom{s + k}{p}(−1)^{k} = (−1)^{r}\binom{s}{p − r}

to obtain

G^{p}(z, y) = z^{p}y^{p} + p ∑_{p≤λ≤n} z^{n}y^{λ} \frac{1}{n}\binom{n}{λ}\binom{n − p − 1}{λ − p}.

Finally we can observe that

F (z, y) = G(z, y) − zy + z = G(zy, y^{−1}),

and obtain thus the announced formula.

Lemma 2. Let A_{k}(z) be the generating function of trees of height ≤ k and set, as before, z = u/(1 + u)^{2}. We have

A_{k}(z) = \frac{u}{1 + u} · \frac{1 − u^{k}}{1 − u^{k+1}} .

Proof. Translating the symbolic equation for the family P, we obtain

A_{k} = \frac{z}{1 − A_{k−1}} , k ≥ 1, A_{0} = 0;

from this we can prove the formula easily by induction . □

Lemma 3. Let Q_{k}(z, y) be the generating function, where [z^{n}y^{m}]Q_{k} is the number of trees of size n with m nodes at level k, which is the maximal level. (This means that, if m ≥ 1, the height of the tree is exactly k.) We have for k ≥ 1 and d ≥ 1

[y^{d}]Q_{k}(z, y) = A_{k−1}^{d+1}(z) − A_{k−1}^{d}(z) + zA_{k−1}^{d−1}(z).

Proof. Translating as usual, we obtain

Q_{1} = zy  and  Q_{k} = \frac{z}{1 − Q_{k−1}} for k ≥ 2.

Since we have

[y^{0}]Q_{k}(z, y) = A_{k−1}(z),

it is sufficient to show that

Q_{k}(z, y) = A_{k−1}(z) + ∑_{d≥1} y^{d}(A_{k−1}^{d+1}(z) − A_{k−1}^{d}(z) + zA_{k−1}^{d−1}(z))

= \frac{A_{k−1}}{1 − yA_{k−1}} − \frac{yA_{k−1}}{1 − yA_{k−1}} + \frac{zy}{1 − yA_{k−1}}

= \frac{(1 − y)A_{k−1} + zy}{1 − yA_{k−1}} ;

this is a simple exercise, using the recurrence for the A_{k}’s.

Let B_{d,k}(z) be the generating function where [z^{n}]B_{d,k} is the number of trees of size n with d leaves having a height > k and all the others having a height ≤ k. We can observe that B_{0,k} + B_{1,k} + ⋯ + B_{d−1,k} is the generating function of trees where d-th highest leaf (in the sense described above) has a height ≤ k. Thus the quantity h_{n}(d) is given by

h_{n}^{(d)} = \frac{[z^{n}] ∑_{k≥0} (P (z) − B_{0,k}(z) − B_{1,k}(z) − ⋯ − B_{d−1,k}(z))}{[z^{n}] P (z)}.

Summerschool Ile de Ré (English version) 14 Lemma 4. The average height of a planted plane tree of size n verifies

\frac{[z^{n}] ∑_{k≥0} (P (z) − B_{0,k}(z))}{[z^{n}] P (z)} ∼ \sqrt{πn} − \frac{1}{2} + ….

Idea of proof. We find that

∑_{k≥0} (P (z) − B_{0,k}(z)) = ∑_{k≥0} (P (z) − A_{k}(z))

= \frac{1 − u}{1 + u} ∑_{k≥1} \frac{u^{k}}{1 − u^{k}} = \frac{1 − u}{1 + u} ∑_{k≥1} d(k)u^{k}

where d(k) is the number of divisors of k. We observe that

∑_{k≥1} d(k)k^{−s} = ζ^{2}(s),

and use the Mellin transform as in Section 2.

As is the Sections 2 and 3 we are going to show that

∑_{k≥0} B_{s+1,k}(z) ∼ A_{s} − B_{s}t + …,

where A_{s} and B_{s} are constants and u = e^{−t}. Since

P (z) = \frac{u}{1 + u} ∼ \frac{1}{2} − \frac{1}{4}t + …,

we can conclude that

[z^{n}] ∑_{k≥0} B_{s+1,k}(z)/t_{n} ∼ 4B_{s}.

Lemma 5. We have for s ≥ 0

∑_{n≥p} z^{n}\binom{n}{s}\binom{n − p}{s} = ∑_{j=0}^{s} \frac{z^{s+p+j}}{(1 − z)^{s+1+j}} \frac{(p + s)!(s + j)!}{j!(s − j)!(p + j)!s!}.

Proof. With D = d/dz and (n)_{d} = n(n − 1) … (n − d + 1) we have

∑_{n≥p} z^{n}\binom{n}{s}\binom{n − p}{s} = \frac{1}{(s!)^{2}} ∑_{n≥0}(n)_{s}z^{s}D^{s}z^{n+p}

= \frac{1}{(s!)^{2}} z^{s}D^{s}z^{p+s} ∑_{n≥0} z^{n}

= \frac{1}{s!}z^{s}D^{s} \frac{z^{p+s}}{(1 − z)^{s+1}}

= \frac{1}{s!}z^{s} ∑_{j=0}^{s} \binom{s}{j}[D^{s−j}z^{p+s}][D^{j}(1 − z)^{−s−1}]. □

Summerschool Ile de Ré (English version) 15 Lemma 6. We have for s ≥ 0 and k ≥ 1

B_{s+1,k}(z) = ∑_{j=0}^{s} \frac{(s + j)!}{j!(s − j)!(s + 1)!} (\frac{u}{1 + u + u^{2}} )^{s+1+j}

× \frac{(1 − u)^{2}}{1 + u} \frac{u^{k−1}}{(1 − u^{k−1})(1 − u^{k})} ∑_{p≥1} \frac{p(p + s)!}{(p + j)!}A_{k−1}^{p}.

Proof. We replace each leaf at maximal level k (marked by y in Q_{k}(z, y)) by an arbitrary tree whose leaves are marked by y. Now

B_{s+1,k} = [y^{s+1}] Q_{k}(z, \frac{1}{z}F (z, y))

= [y^{s+1}] ∑_{p≥1} [\frac{1}{z}F (z, y)]^{p}[A_{k−1}^{p+1} − A_{k−1}^{p} + zA_{k−1}^{p−1}]

= ∑_{p≥1} z^{−p}p ∑_{n≥1} z^{n} \frac{1}{n}\binom{n}{s + 1}\binom{n − p − 1}{s}A_{k−1}^{p}[A_{k−1} − 1 + zA_{k−1}^{−1}].

The announced formula is now obtained by remarking that

A_{k−1} − 1 + zA_{k−1}^{−1} = \frac{u^{k−1}}{(1 − u^{k−1})(1 − u^{k})} \frac{(1 − u)^{2}}{1 + u} ,

\frac{z}{1 − z} = \frac{u}{1 + u + u^{2}}

and using Lemma 5. Lemma 7. The generating function B_{s+1,k}(z) is given by

B_{s+1,k}(z) = ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}×

× (\frac{u}{1 + u + u^{2}} )^{s+1+j} (1 − u)^{2}u^{i+1}u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}} .

Proof. We use the formula (being a consequence of the Vandermonde formula)

\frac{p(p + s)!}{(s − j)!(s + 1)!(p + j)!} = ∑_{i=0}^{s−j}(i + 1)\binom{p}{i + 1}\frac{1}{(s − j − i)!(j + i + 1)!}

and also the equations

\frac{A_{k}}{z} = \frac{1}{1 − A_{k−1}}

and

∑_{p≥1} \binom{p}{i + 1}A_{k−1}^{p} = \frac{A_{k−1}^{i+1}}{(1 − A_{k−1})^{i+2}} .

Now we are ready to attack the local expansion of ∑_{k≥0} B_{s+1,k}. We easily see that

\frac{u}{1 + u + u^{2}} ∼ \frac{1}{3};  (1 − u)^{2} ∼ t^{2}(1 − t);  u^{i+1} ∼ 1 − (i + 1)t.

Lemma 8. We have the local expansion

∑_{k≥0} u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}}

∼ t^{−2}(1 + 2t)( ∑_{l=0}^{i} \binom{i}{l}(−2)^{l}(1 + lt)(ζ(l + 2) − \frac{l}{2}ζ(l + 1)t) − \frac{1}{2}t).

Proof. We can write

∑_{k≥0} u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}} = u^{−2} ∑_{k≥1} \frac{u^{k}}{(1 − u^{k})^{2}} (1 + \frac{(1 − u^{−2})u^{k}}{1 − u^{k}} )^{i}

= u^{−2} ∑_{l=0}^{i} \binom{i}{l}(1 − u^{−2})^{l} ∑_{k≥1} \frac{u^{k(l+1)}}{(1 − u^{k})^{l+2}} .

It is easy to see that

u^{−2} ∼ 1 + 2t  and  (1 − u^{−2})^{l} ∼ (−2)^{l}t^{l}(1 + lt).

We use again the Mellin transform:

M ∑_{k≥1} \frac{e^{−tk(l+1)}}{(1 − e^{tk})^{l+2}} = ∑_{k≥1} k^{−s}M\frac{e^{−t(l+1)}}{(1 − e^{t})^{l+2}}

= ζ(s)Γ(s) ∑_{λ≥0} \binom{λ}{l + 1}λ^{−s}

= ζ(s)Γ(s) ∑_{λ≥0} \frac{1}{(l + 1)!} ∑_{i=0}^{l+1} s_{l+1,i}λ^{i}λ^{−s}

(where the s_{l+1,j} are Stirling numbers of the first kind)

= \frac{1}{(l + 1)!}ζ(s)Γ(s) ∑_{i=0}^{l+1} s_{l+1,i}ζ(s − i).

As in Secion 2 we use the Mellin inversion formula; change the line of integration and take the residues into account. In our problem is sufficient to consider the terms where i = s + 1 and i = s. We note that

s_{l+1,l+1} = 1  and  s_{l+1,l} = −\binom{l + 1}{2}.

Lemma 9. The sum of the B_{s+1,k}(z) has to local expansion

∑_{k≥0} B_{s+1,k}(z) ∼ const − \frac{1}{2}t ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

Idea of proof.

∑_{k≥0} B_{s+1,k}(z) ∼ ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}t^{2}(1 − t)(1 − (i + 1)t)×

× t^{−2}(1 + 2t)( ∑_{l=0}^{i} \binom{i}{l}(−2)^{l}(1 + lt)(ζ(l + 2) − \frac{l}{2}ζ(l + 1)t) − \frac{1}{2}t)

We want to obtain the coefficient of t in this expression. This is a simple thing; after some manipulations there are luckily of lot of simplifications . □

From the preceeding equations we deduce

[z^{n}] B_{s+1,k}(z)/t_{n} ∼ 4 · \frac{1}{2} ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

For the quantity h_{n}^{(d)} we have to sum up:

∑_{s=0}^{d−2} 2 ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

We can rewrite this quantity as

∑_{s=0}^{d−2} \frac{2}{(s + 1)3^{s+1}} [x^{s}] \frac{1}{(1 − x)^{2}} (\frac{1 + x}{1 − \frac{x}{3}} )^{s+1} .

Thus we have finally obtained

Theorem 3. The average height of the d-th highest leaf of a planted plane tree of size n, has the following asymptotic expansion (for d fixed and n → ∞)

h_{n}^{(d)} = \sqrt{πn} − \frac{1}{2} − ∑_{s=0}^{d−2} \frac{2}{(s + 1)3^{s+1}} [x^{s}] \frac{1}{(1 − x)^{2}} (\frac{1 + x}{1 − \frac{x}{3}} )^{s+1} + o(1).

5. Some remarks concerning the technique of the extraction of coefficients

If one follows the strategy mentioned in the title, the enumeration problems for trees often involve the evaluation of sums of the type

∑_{k≥1} ω(k)\frac{\binom{2n}{n+k+1} − 2\binom{2n}{n+k} + \binom{2n}{n+k−1}}{\binom{2n}{n}}.

where ω(k) might be, for example, v_{2}(k) or ϑ(k) or d(k) as in Sections 2, 3 and 4.

One needs to approximate certain binomial coefficients in a central region (e.g. |k| ≤ \sqrt{n} log n). We obtain, for instance by Stirling’s formula,

\begin{matrix}( & {2n \atop n+k} & ) \\ ( & {2n \atop n} & ) \end{matrix} ∼ e^{−k^{2}/n} · (1 + \frac{k^{2}}{2n^{2}} − \frac{k^{4}}{6n^{3}} + …)

(see [9] for a general formula). Quite often r-th differences of binomal coefficients appear, viz.

ξ = [u^{n}] u^{k}(1 − u)^{r}(1 + u)^{2n}/\binom{2n}{n} = ∑_{λ=0}^{r}(−1)^{λ}\binom{r}{λ}\binom{2n}{n + k + r}/\binom{2n}{n}.

Let us recall the difference operator Δ:

Δ^{r}\binom{2n}{n + k} = ∑_{λ=0}^{r} \binom{r}{λ}(−1)^{r−λ}\binom{2n}{n + k + λ}

Let us consider Δ^{r}e^{−k^{2}/n}. For this, we need the Hermite polynomials. Here are the necessary properties [3]:

e^{2zt−t^{2}} = ∑_{n≥0} H_{n}(z)\frac{t^{n}}{n!}

H_{0} = 1, H_{1} = 2z, H_{n+1} = 2zH_{n} − 2nH_{n−1}

H_{n}(z) = ∑_{k≥0} \frac{n!}{k!(n − 2k)!}(−1)^{k}(2z)^{n−2k}

H_{n}(−z) = (−1)^{n}H_{n}(z)

Thus

Δ^{r}e^{−k^{2}/n} = ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}e^{−(k+λ)^{2}/n}

= e^{−k^{2}/n} ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}e^{− \frac{2kλ}{n} − \frac{λ^{2}}{n}}

= e^{−k^{2}/n} ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ} ∑_{m≥0} H_{m} (−\frac{k}{\sqrt{n}}) (\frac{λ}{\sqrt{n}})^{m} \frac{1}{m!}.

We know (with Stirling numbers of the second kind) that

∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}λ^{m} = r!S_{m,r}.

Hence

(−1)^{r}Δ^{r}e^{−k^{2}/n} ∼ e^{−k^{2}/n} [H_{r} (\frac{k}{\sqrt{n}}) \frac{1}{n^{r/2}} − H_{r+1} (\frac{k}{\sqrt{n}}) \frac{1}{n^{(r+1)/2}} \frac{r}{2} + …] .

Therefore we have

ξ ∼ e^{−k^{2}/n}H_{r} (\frac{k}{\sqrt{n}}) \frac{1}{n^{r/2}} ,

which was already announced in [5].

To obtain more terms we have to consider Δ^{r}k^{t}e^{−k^{2}/n}.

We can use the general formula (of Leibniz type):

Δ^{r}f(k)g(k) = ∑_{λ=0}^{r} \binom{r}{λ}(Δ^{r−λ}f(k + λ))(Δ^{λ}g(k))

with f(k) = k^{t} and g(k) = e^{−k^{2}/n}.

If we have to consider (for a certain polynomial p)

[u^{n}] u^{k}p(u)(1 + u)^{2n},

we can developp p(u) in powers of 1 − u and use the just described machinery.

In a lot of other cases we must investigate the quantities

[u^{n}] u^{k} \frac{1}{1 − u}(1 + u)^{2n};

for this we have to consider

∑_{j≥k} e^{−j^{2}/n} ∼ \sqrt{n} erfc (\frac{k}{\sqrt{n}}) + \frac{1}{2}e^{−k^{2}/n} + …,

which comes for Euler’s summation formula and the error function

erfc(z) := ∫_{z}^{∞} e^{−t^{2}}dt.

To obtain more terms, we must consider

I_{m}(z) = ∫_{z}^{∞} t^{m}e^{−t^{2}}dt;

we can evaluate this integral by partial integration:

I_{m}(z) = \frac{m − 1}{2}I_{m−2}(z) + \frac{1}{2}z^{m−1}e^{−z^{2}},

I_{1}(z) = \frac{1}{2}e^{−z^{2}}, I_{0}(z) = erfc(z).

Finally a more general problem of the same nature appears in the evaluation of sums of the type

[u^{n}] u^{k} \frac{1}{(1 − u)^{a}} (1 + u)^{2n}

where a is an integer ≥ 1.

Summerschool Ile de Ré (English version) 20

References

1. de Bruijn, Knuth, Rice, The average height of planted plane trees, Graph Theory and Computing (R.C. Read, eds.), Academic Press, New York, 1972, pp. 15–22.

2. Dieudonne, Calcul Infinitesimal, Hermann, Paris, 1968.

3. Erdelyi, Magnus, Oberhettinger, Tricomi, Higher Transcendental Functions, Mc-Graw-Hill, 1955.

4. Flajolet, Analyse d’algorithmes d’arbres and de fichiers, Cahiers du BURO 34–35 (1981), 1–209.

5. Flajolet, Raoult, Vuillemin, The number of registers required for evauluating arithmetic expressions, Theor. Comput. Sci. 9 (1979), 99–125.

6. Flajolet, Ramshaw, A note on Gray Code and odd-even merge, SIAM J. on Computing 9 (1980), 142–158.

7. Flajolet, Odlyzko, The average height of binary trees and other simple trees, J. Comput. Syst. Sci. 25 (1982), 171–213.

8. Flajolet, Prodinger, Register Allocation for unary-binary Trees, SIAM J. on Computing 15 (1986), 629–640.

9. Greene, Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1981.

10. Jungen, Sur les series de Taylor n’ayant que des singularites algebro-logarithmiques sur leur cercle de convergence, Commentarii Math. Helvetici 3 (1931), 266–306.

11. Kemp, The average number of registers to evaluate a binary tree optimally, Acta. Inf. 11 (1979), 363–372.

12. Kemp, On the average oscillation of a stack, Combinatorica 2 (1982), 157–176.

13. Kemp, The average height of planted plane trees with m leaves, Journal of Combinatorial Theory Ser. B B 34 (1983), 191–208.

14. Kemp, On the number of deepest nodes in ordered trees, Discrete Mathematics 81 (1990), 247–258.

15. Knuth, The Art of Computer Programming,Vol.1, Addison-Wesley, 1968.

16. Knuth, The Art of Computer Programming,Vol.3, Addison-Wesley, 1968.

17. Meir, Moon and Pounder, On the order of random channel networks, SIAM J. on Alg. Disc. Meth. 1 (1980), 25–33.

18. Prodinger, The average height of the second highest leaf of a planted plane trees, Europ. J. on Combinatorics 5 (1984), 351–357.

19. Prodinger, Die Bestimmung gewisser Parameter von binären Bäumen mit Hilfe analytischer Methoden, Lecture Notes in Mathematics (E.Hlawka, Ed.) 1114 (1985), 118–133.

20. Prodinger, The Average Height of the d-th Highest Leaf of a Planted Plane Tree, Networks 16 (1985), 67–75.

21. Sedgewick, Data movement in odd-even merge, SIAM J. on Computing 7 (1978), 239–272.

22. Whittaker, Watson, A course in modern analyis, Cambridge University Press, 1930.