Michael Drmota

Bernhard Gittenberger

The width of Galton-Watson trees conditioned by the size †

Keywords: Galton-Watson branching process, width, moment convergence theorem, Brownian excursion

It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ 2 are asymptotically given by (σ √ n) p m p where m p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and a tightness estimate. The method is quite general and we state some further applications.

Introduction

In this paper we are considering rooted trees which are family trees of a Galton-Watson branching process conditioned to have total progeny n. These trees are also called simply generated trees (see [START_REF] Meir | On the altitude of nodes in random trees[END_REF]). Without loss of generality we may assume that the offspring distribution ξ is given by

P {ξ = k} = τ k ϕ k ϕ(τ) , (1)
where (ϕ k ; k ≥ 0) is a sequence of non-negative numbers such that ϕ 0 > 0 and ϕ(t) = ∑ k≥0 ϕ k t k has a positive or infinite radius of convergence R and τ is an arbitrary positive number within the circle of convergence of ϕ(t). These conditions in particular imply that all moments of ξ exist and that τ < R. Due to conditioning on the total progeny and finiteness of moments it is no restriction if we confine ourselves to studying only the critical case, that is, E ξ = 1 which equivalently means that τ satisfies τϕ ′ (τ) = ϕ(τ).

The variance of ξ can also be expressed in terms of ϕ(t) and is given by

σ 2 = τ 2 ϕ ′′ (τ) ϕ(τ) . (2)
Note that the offspring distribution (1) can be interpreted as assigning weights to all trees defined by

ω(T ) = ∏ k≥0 ϕ n k (T ) k
for a tree T having n nodes, n k of which have out-degree k, k ≥ 0. Denote by |T | the number of nodes of such a tree and let a n be the (weighted) number of all trees with n nodes, i.e.

a n = ∑ T :|T |=n ω(T ).

Then the corresponding generating function a(z) = ∑ n≥0 a n z n satisfies the functional equation a(z) = zϕ(a(z)).

(

) 3
Denote by (L n (t),t ≥ 0) the sequence of the generation sizes of a Galton-Watson tree the total progeny of which is n. For non-integer t we define L n (t) by linear interpolation:

L n (t) = (⌊t⌋ + 1 -t)L n (⌊t⌋) + (t -⌊t⌋)L n (⌊t⌋ + 1), t ≥ 0.
We are interested in the width of such a tree which is defined by

w n = max t≥0 L n (t).
This quantity attracted the interest of many authors. First, Odlyzko and Wilf [START_REF] Odlyzko | Bandwidths and profiles of trees[END_REF] became interested in this tree parameter when studying the bandwidth

β(T ) = min f max (u,v)∈E(T ) | f (u) -f (v)|
of a tree T , where f is an assignment of distinct integers to the vertices of the tree. They showed for a tree with n vertices and height h(T ) and width w(T ) that

n -1 2h(T ) ≤ β(T ) ≤ 2w(T ) -1
and furthermore they showed that there exist positive constants c 1 and c 2 such that the estimate

c 1 √ n < E w n < c 2 n log n (4)
holds. The exact order of magnitude was left as an open problem. Aldous conjectured [START_REF] Aldous | The continuum random tree. II. An overview[END_REF]Conj. 4] that L n (suitably normalized) converges to Brownian excursion local time. This was first proved in [START_REF] Drmota | On the profile of random trees[END_REF], later by different methods by Kersting [29] and Pitman [START_REF] Pitman | The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest[END_REF]. More precisely, set

l n (t) = 2 σ √ n L n 2t σ √ n and l(t) = lim ε→0 1 ε 1 Z 0 I [t,t+ε] (W (s)) ds,
where (W (s), 0 ≤ s ≤ 1) is the standard scaled Brownian excursion. l(t) is the local time (at time 1 and level t) of the normalized Brownian excursion. Then the above described limit theorem reads as follows:

Theorem 1 ([15]

). Let ϕ(t) be the GF of a family of random trees. Assume that ϕ(t) has a positive or infinite radius of convergence R. Furthermore suppose that the equation tϕ ′ (t) = ϕ(t) has a minimal positive solution τ < R. Then we have

(l n (t),t ≥ 0) w -→ (l(t),t ≥ 0) in C[0, ∞), as n → ∞.
Partial results go back to [START_REF] Cohen | Brownian excursion, the M/M/1 queue and their occupation times[END_REF][START_REF] Getoor | Excursions of Brownian motion and Bessel processes[END_REF][START_REF] Hooghiemstra | On the explicit form of the density of Brownian excursion local time[END_REF][START_REF] Louchard | Kac's formula, Levy's local time and Brownian excursion[END_REF][START_REF] Takács | Brownian local times[END_REF]. The density of the finite dimensional distributions of l was computed in [START_REF] Gittenberger | The Brownian excursion multi-dimensional local time density[END_REF]. A consequence of Theorem 1 is the following result which was proved directly by Takács [START_REF] Takács | Limit distributions for queues and random rooted trees[END_REF].

Corollary 1 ([15]). Under the assumptions of Theorem 1 we have

sup t≥0 l n (t) w -→ sup t≥0 l(t).

Thus this suggests (but does not imply)

√ n as correct order of magnitude in (4).

Note that the maximum of local time is well studied (cf. [START_REF] Kennedy | The distribution of the maximum Brownian excursion[END_REF][START_REF] Lai | Excursions in Brownian motion[END_REF][START_REF] Durrett | Weak convergence to Brownian meander and Brownian excursion[END_REF][START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF][START_REF] Louchard | Kac's formula, Levy's local time and Brownian excursion[END_REF]). We have

sup t≥0 l(t) d = 2 sup 0≤t≤1 W (t),
moreover it is theta-distributed, i.e.,

P sup 0≤t≤1 l(t) ≤ x = 1 -2 ∑ k≥1 (x 2 k 2 -1)e -x 2 k 2 /2 , x > 0,
and

E sup t≥0 l(t) p = 2 p/2 p(p -1)Γ p 2 ζ(p).
The purpose of this paper is to show that, in addition to the weak limit theorem above, we have a moment convergence theorem of sup t≥0 l n (t) to sup t≥0 l(t), too. We formulate it in terms of the width

w n = max t≥0 L n (t) = (σ/2) √ n sup t≥0 l n (t).
Theorem 2. Suppose that there exists a minimal positive solution τ < R of tϕ ′ (t) = ϕ(t). Then the width w n satisfies

E (w p n ) = σ p 2 -p/2 p(p -1)Γ p 2 ζ(p) • n p/2 • (1 + o(1))
as n → ∞.

It should be further mentioned that Chassaing and Marckert [START_REF] Chassaing | Parking functions, empirical processes, and the width of rooted labeled trees[END_REF] used the relation of parking functions and rooted trees as well as the strong convergence theorem of Komlos, Major and Tusnady [START_REF] Komlós | An approximation of partial sums of independent RV's, and the sample DF. II. Z. Wahrscheinlichkeitstheorie und Verw[END_REF] to derive tight bounds for the moments of the width for Cayley trees. They showed (here and throughout the whole paper, a ≪ b denotes a ≤ C b for some positive constant C)

Theorem 3 ([7]). If ϕ(t) = e t and p ≥ 1, then E w n σ √ n p -E 1 2 sup t≥0 l(t) p = E w n σ √ n p -E (sup t≥0 W (t)) p ≪ n -p/4 log n.
Remark. In fact, Chassaing and Marckert [START_REF] Chassaing | Parking functions, empirical processes, and the width of rooted labeled trees[END_REF] showed an even stronger result: In some probability space there exist a sequence of copies of w n and a sequence of theta-distributed random variables D n such that for any

p ≥ 1 2w n σ √ n -D n p = O n -1/4 log n
where the O-constant depends on p.

Recently, Chassaing, Marckert, and Yor [START_REF] Chassaing | The height and width of simple trees[END_REF] have used Theorems 1 and 3 in conjunction with results of Aldous [START_REF] Aldous | The continuum random tree. II. An overview[END_REF] to obtain a weak limit theorem (without moments) for the joint law of height and width of simply generated trees. (For binary trees they present an elementary proof, too.)

Plan of the Proof of Theorem 2

In view of Corollary 1 the result of Theorem 2 is not unexpected. Nevertheless, it does not follow directly from Corollary 1 since convergence of moments is not automatically transfered via weak convergence (from Theorem 1).

In order to prove Theorem 2 we actually use the result of Theorem 1, that is, the normalized profile of Galton-Watson trees converges weakly to Brownian excursion local time: (l n (t),t ≥ 0) w -→ (l(t),t ≥ 0). However, we need some additional considerations: In [START_REF] Drmota | Reinforced weak convergence of stochastic processes[END_REF] (see also [START_REF] Drmota | Stochastic analysis of tree-like data structures[END_REF]) Drmota and Marckert introduced the notion of so-called polynomial convergence (that is inspired by the notion of uniform integrability).

The key property for our purposes is the following one. It generalizes the results of [START_REF] Drmota | Reinforced weak convergence of stochastic processes[END_REF] (see also [START_REF] Drmota | Stochastic analysis of tree-like data structures[END_REF]Theorem 3.7]) that only apply for processes with compact support.

Theorem 4. Let x n be a sequence of stochastic processes in C[0, ∞) which converges weakly to x. Assume that for any choice of fixed positive integers p and d there exist positive constants c

0 , c 1 , c 2 , c 3 such that sup n≥0 E |x n (t)| p ≤ c 0 e -c 1 t for all t ≥ 0, ( 5
)
and

sup n≥0 E |x n (t + s) -x n (t)| 2d ≤ c 2 e -c 3 t s d for all s,t ≥ 0. ( 6
)
Then x n is polynomially convergent to x, that is, for every continuous functional F :

C[0, ∞) → R of polynomial growth (i.e. |F(y)| ≪ (1 + y ∞ ) r for some r ≥ 0) we have lim n→∞ E F(x n ) = E F(x).
We will show that l n satisfies the assumptions ( 5) and ( 6) of Theorem 4 and thus taking

F(x) = x r ∞ yields immediately Theorem 2.
The next section is devoted to the proof of Theorem 4. In sections 4 and 5 we prove ( 5) and [START_REF] Chassaing | The height and width of simple trees[END_REF]. Finally in section 6 we provide some further applications of Theorem 4.

Proof of Theorem 4

Let us start with the following two observations. Lemma 1. Suppose that x n satisfies [START_REF] Billingsley | Probability and measure[END_REF]. Then for every p ≥ 0 we have

E sup j∈N |x n ( j)| p ≪ 1
uniformly for all n.

Proof. Since E |x n (t)| p+1 ≪ e -c 1 t , uniformly in n, we have

P sup j∈N |x n ( j)| ≥ A ≤ ∑ j≥0 P {|x n ( j)| ≥ A} ≤ 1 A p+1 ∑ j≥0 E |x n ( j)| p+1 by Markov's inequality ≪ 1 A p+1 ∑ j≥0 e -c 1 j ≪ 1 A p+1
Thus it follows that

E sup j∈N |x n ( j)| p ≪ 1 + p Z ∞ 1 A p-1 1 A p+1 dA ≪ 1.
Lemma 2. Suppose that x n satisfies [START_REF] Chassaing | The height and width of simple trees[END_REF]. Then, for fixed p we have

E sup |s-t|≤δ |x n (s) -x n (t)| p ≪ δ p/2 .
uniformly for δ with 0 < δ < 1 and for all n.

Proof. First we prove that for every integer d > 1 there exists a constant K > 0 such that for ε > 0 and 0 < δ < 1

P sup |s-t|≤δ |x n (s) -x n (t)| ≥ ε ≤ K δ d-1 ε 2d . (7)
Arguing as in [4, pp. 95] guarantees that there exists a constant K 1 > 0 such that for all m ≥ 0

P sup |s-t|≤δ,m≤s,t≤m+2 |x n (s) -x n (t)| ≥ ε ≤ K 1 e -c 5 m δ d-1 ε 2d . Thus P sup |s-t|≤δ |x n (s) -x n (t)| ≥ ε ≤ ∞ ∑ m=0 K 1 e -c 5 m δ d-1 ε 2d ≤ K δ d-1 ε 2d for some constant K > 0. Set Z = sup |s-t|≤δ |x n (s) -x n (t)|.
Then by applying [START_REF] Chassaing | Parking functions, empirical processes, and the width of rooted labeled trees[END_REF] it follows that (if 2d ≥ p + 1)

E Z p =p Z ∞ 0 z p-1 P[Z > z] dz =p Z (Kδ) (d-1)/d 0 z p-1 P[Z > z] dz + p Z ∞ (Kδ) (d-1)/d z p-1 P[Z > z] dz ≤(Kδ) p(d-1)/d + pKδ d-1 Z ∞ (Kδ) (d-1)/d z p-1-2d dz ≪δ p(d-1)/d ≤ δ p/2 ,
which proves the Lemma.

The proof of Theorem 4 is now an easy task. Note that the results of Lemma 1 and 2 in conjunction with the triangular inequality imply

sup n≥0 E sup t≥0 |x n (t)| r < ∞ for all r ≥ 0.
Thus, if F is a continuous functional of polynomial growth we have for any ε > 0

sup n≥0 E |F(x n )| 1+ε < ∞.
By continuity of F we also obtain F(x n ) w -→ F(x) and finally, by Billingsley [5,p. 338] it directly follows that lim

n→∞ E F(x n ) = E F(x)
as desired. ✷

Moments for the Profile of Galton-Watson Trees

We start with a lemma on the growth of coefficients of powers of certain generating functions.

Lemma 3. Let z 0 = 0 and ∆ = {z : |z| < z 0 +η, | arg(z-z 0 )| > ϑ},
where η > 0 and 0 < ϑ < π/2. Suppose that f (z) and g(z) are analytic functions in ∆ which satisfy

| f (z)| ≤ exp -C 1 - z z 0 , z ∈ ∆, g(z) =1 -D 1 - z z 0 + O 1 - z z 0 , z ∈ ∆,
for some positive constants C, D. Then for any fixed ℓ there exists a constant C ′ > 0 such that

[z n ] f (z) r (1 -g(z)) ℓ = O e -C ′ r/ √ n n (ℓ-2)/2
uniformly for all r, n ≥ 0 (where [z n ]F(z) denotes the coefficient of z n of the function F(z)).

Proof. The only difference to [START_REF] Gittenberger | On the contour of random trees[END_REF]Lemma 3.5] is the factor 1/(1g(z)) ℓ , but since its behavior in ∆ is known and [20, Theorem 3] is applicable, the proof is analogous to that of [START_REF] Gittenberger | On the contour of random trees[END_REF]Lemma 3.5].

By means of this lemma we can show

Lemma 4. For every fixed integer p > 0 there exist positive constants c 0 and c 1 such that

sup n≥0 E l n (t) p ≤ c 0 e -c 1 t (8)
for all t ≥ 0.

Proof. For technical simplicity we assume that g = gcd{i ≥ 1 :

ϕ i > 0} = 1.
This assumption ensures that the tree function a(z) defined by (3) has only one singularity z 0 = 1/ϕ ′ (τ) on the circle of convergence.

If g = gcd{i ≥ 0 : ϕ i > 0} > 1 then we can use the substitution x = z 1/g to get a(z) = xb(x) where b(x) is analytic with only one singularity on the circle of convergence. Thus this case reduces to the case g = 1. The other possibility is to deal with the g singularities z 0 e 2πi j/g , j = 0, 1, . . . , g -1, on the circle of convergence and add all contributions.

In particular, it is also well known that (if g = 1) a(z) admits a representation of the following kind

a(z) = τ - τ √ 2 σ 1 - z z 0 + O 1 - z z 0 , (9)
that is valid for |z| < z 0 + η and arg(zz 0 ) = 0, where η > 0 is suitably small, compare with [START_REF] Meir | On the altitude of nodes in random trees[END_REF] and [START_REF] Drmota | Systems of functional equations[END_REF].

In what follows we will need the local expansion of α(z) = zϕ ′ (a(z)). From (9) we immediately get

α(z) = 1 -σ √ 2 1 - z z 0 + O 1 - z z 0 (10)
for |z| < z 0 + η and arg(zz 0 ) = 0. Due to [START_REF] Drmota | Distribution of the height of leaves of rooted trees[END_REF] there exists a constant

C > 0 such that |α(z)| ≤ exp -C |1 -z/z 0 | for z ∈ ∆ (with ∆ from Lemma 3). Furthermore, it follows that sup z∈∆ |α(z)| = 1, ( 11
)
where we have to choose η > 0 and 0 < ϑ < π/2 in a proper way. First, since the power series of α(z) has only positive coefficients, we have max |z|≤z 0 |α(z)| = 1. If we assume that d = gcd{i ≥ 1 :

ϕ i > 0} = 1 it also follows that max |z|≤z 0 ,|z-z 0 |≥ε |α(z)| < 1
for every ε > 0. Now, in the vicinity of the singularity z 0 , that is, for |zz 0 | < ε we can again use [START_REF] Drmota | Distribution of the height of leaves of rooted trees[END_REF] and get for z = z 0 (1 + te iθ )

α 1 + te iθ = 1 -σ √ 2te ±i(π-θ)/2 + O (t) , (12)
where θ > π/2. Hence we have |α(z)| ≤ 1 for |zz 0 | ≤ ε and | arg(zz 0 )| > θ. Finally, for |z| ≤ z 0 + η and |zz 0 | ≥ ε we obtain the same inequality from ( 12) by a continuity argument (for some sufficiently small η > 0). This proves [START_REF] Drmota | Correlations on the strata of a random mapping[END_REF]. Now observe that by substituting r = ⌊t √ n⌋ in [START_REF] Lai | Excursions in Brownian motion[END_REF] we get

E L n (r) p ≤ c 0 e -c 1 r/ √ n n p/2 . ( 13
)
Furthermore note that it suffices to show [START_REF] Drmota | Systems of functional equations[END_REF] for the pth factorial moment

E [L n (r)] p = E L n (r)(L n (r) -1) • • • (L n (r) -p + 1)
instead of the pth moment, which we can easily express in terms of the proper coefficient of a generating function. Indeed we have

E [L n (r)] p = 1 a n [z n ] ∂ ∂u p y r (z, ua(z)) u=a(z)
, where

y 0 (z, u) = u y i+1 (z, u) = zϕ(y i (z, u)), i ≥ 0. ( 14
)
In order to evaluate this coefficient we use Lemma 3 which translates the local behavior of the function near its singularity into an asymptotic estimate for the coefficients.

By [24, p. 287, equ. (22)] we have

∂ ∂u p y r (z, ua(z)) u=a(z) = O a(z) p |α(z) r | 1 -α(z) r 1 -α(z) p-1 . (15)
From ( 11) we get

max z∈∆ 1 -α(z) r 1 -α(z) ≤ r. ( 16
)
Moreover a(z) p behaves like a constant near the singularity and α(z) r meets the condition in Lemma 3.

Hence the last factor in ( 15) is bounded by r p-1 and hence contributes a factor n (p-1)/2 to the order of magnitude of the pth factorial moment E [L n (r)] p . Applying Lemma 3, which yields exp(-c 1 r/ √ n ), and normalizing by a n ∼ τ/σz n 0 √ 2πn 3 we get the desired result.

Quantitative Tightness Estimates

With help of Lemma 3 we can prove the following quantitative tightness estimate.

Lemma 5. For every fixed positive integer d there exist constants c 2 , c 3 such that for every s,t > 0

E |l n (t + s) -l n (t)| 2d ≤ c 2 e -c 3 t s d . (17)
Proof(Sketch). Observe that we can rewrite [START_REF] Drmota | Reinforced weak convergence of stochastic processes[END_REF] as

E |L n (r) -L n (r + h)| 2d ≤ c 2 e -c 3 r/ √ n h d n d/2 (18)
which is quite similar to [START_REF] Drmota | On the profile of random trees[END_REF]Theorem 6.1]. From [START_REF] Drmota | On the profile of random trees[END_REF] it follows that

E |L n (r) -L n (r + h)| 2d = 1 a n [z n ]H r,h (z), in which H r,h (z) = u ∂ ∂u 2d y r (z, uy h (z, u -1 a(z))) u=1
and y(z, u) is given by ( 14). Evaluation of this coefficient is again done by Lemma 3. By [15, Proposition 6.1] it is easy to show that

H r,h (z) = α(z) r d ∑ j=0 G j,rh (z) (1 -α(z) h ) j (1 -α(z)) d-1+ j , (19)
where G j,rh (z) satisfy max

z∈∆ |G j,rh (z)| = O (1) .
Eventually, an application of ( 16), with h instead of r, and Lemma 3 to (19) yields

[z n ]H r,h (z) = O h d n (d-3)/2
z n 0 and, thus, by a n ∼ τ/σz n 0 √ 2πn 3 the proof is complete.

Extensions

Nodes of given degree

In [START_REF] Drmota | On nodes of given degree in random trees[END_REF] the number of nodes with fixed degree d in layers of random trees was investigated. In this case also limit theorems like Theorem 1 and Corollary 1 hold. In fact, we have where w

(d) n = max k≥0 l (d) n (k).
Proof(Sketch).

Part 1 was proved in [START_REF] Drmota | On nodes of given degree in random trees[END_REF]. The proof of part 2 runs similarly to the proof of Theorem 2. The only crucial point is to get estimates as in Lemma 4 and Lemma 5, namely

E L (d) n (r) p ≤ c 1 e -c 2 r/ √ n n p/2 and E L (d) n (r) -L (d) n (r + h) 2d ≤ c 1 e -c 2 r/ √ n h d n d/2 . ( 20
)
Both inequalities can be proved in a similar manner, so let us look at the second one (the first is the easier one). The results in [START_REF] Drmota | On nodes of given degree in random trees[END_REF] imply

E L (d) n (r) -L (d) n (r + h) 2d = 2 σa n [z n ]H (d) 2r/σ,2h/σ (z)
with

H (d) r,h (z) = u ∂ ∂u 2d y r (z, z(u -1)ϕ d-1 y h-1 (z, z(u -1 -1)ϕ d-1 a(z) d-1 + a(z)) y h (z, z(u -1 -1)ϕ d-1 a(z) d-1 + a(z))) u=1
and since the right-hand side of this equation can be expressed in a form similar to [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF], we can easily prove [START_REF] Flajolet | Singularity analysis of generating functions[END_REF]. ✷

Strata of random mappings

A random mapping of size n is an element of the set F n of all mappings of a set with n elements into itself, where F n is equipped with the uniform distribution. These mappings can be represented by functional digraphs consisting of components which are cycles of trees, i.e., each component of this graph contains exactly one cycle and each vertex in this cycle is the root of a tree in which each edge is directed towards the root. The set of points in distance r from a cycle is called the rth stratum of a random mapping. This parameter was previously studied in [START_REF] Aldous | Brownian bridge asymptotics for random mappings[END_REF][START_REF] Drmota | Correlations on the strata of a random mapping[END_REF][START_REF] Drmota | Strata of random mappings-a combinatorial approach[END_REF][START_REF] Ljuben | The limit distribution of the number of nodes in low strata of a random mapping[END_REF][START_REF] Proskurin | The distribution of the number of vertices in the strata of a random mapping[END_REF]. For general results on random mappings and literature see [START_REF] Valentin | Random mappings[END_REF][START_REF] Flajolet | Random mapping statistics[END_REF]. Let M n (r) denote the number of nodes in the rth stratum of a random mapping of size n. Then in [START_REF] Drmota | Strata of random mappings-a combinatorial approach[END_REF] we proved Theorem 6. Let B(t) denote reflecting Brownian bridge, i.e., a process on the interval [0, 1] which is identical in law to |W (s) -sW (1)| (W (t) is the standard Brownian motion), and l (B) (t) its local time, i.e., l (B)

(t) = lim ε→0 1 ε 1 Z 0 I [t,t+ε] (B(s)) ds.
Then we have

(m n (t),t ≥ 0) = 2 √ n M n 2t √ n ,t ≥ 0 w -→ (l (B) (t),t ≥ 0) in C[0, ∞), as n → ∞. Thus we also have sup t≥0 m n (t) w -→ sup t≥0 l (B) (t). (21)
Here again the corresponding moment convergence theorem is not a consequence of [START_REF] Flajolet | Random mapping statistics[END_REF]. However, as before we can show Theorem 7. We have

E sup t≥0 m n (t) p = E sup t≥0 l (B) (t) p (1 + o(1)). ( 22
)
Proof(Sketch). Again the crucial point is to get proper estimates. From [START_REF] Drmota | Strata of random mappings-a combinatorial approach[END_REF] it is an easy exercise to get

E |M n (r) -M n (r + h)| 2d = 2n! n n [z n ]H 2r,2h (z), in which H r,h (z) = u ∂ ∂u 2d 1 1 -y r (z, uy h (z, u -1 a(z))) u=1 .
This function can be written in a form similar to [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF] and thus we can easily prove

E |M n (r) -M n (r + h)| 2d ≤ c 1 e -c 2 r/ √ n h d n d/2
and then [START_REF] Getoor | Excursions of Brownian motion and Bessel processes[END_REF]. The corresponding bound for the moments, obtained in the same way, carries out even easier. ✷

Height of random trees

The same method can be used to re-derive the analogue for the height h n of simply generated trees (see Flajolet and Odlyzko [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF]). as n → ∞.

h n is equal to the maximum of the traversal process T n (r), defined to be the distance between the root and the rth node during preorder traversal of the tree. Obviously, the same holds when we only traverse leaves (call the corresponding process Tn (r)). It is well known (see [START_REF] Aldous | The continuum random tree. II. An overview[END_REF]) that

(X n (t),t ≥ 0) = 1 √ n T n (2tn)t ≥ 0 w -→ 2 σ W (t)t ≥ 0
The height of leaves was investigated by several authors (see [START_REF] Kirschenhofer | On the height of leaves in binary trees[END_REF][START_REF] Kirschenhofer | Some new results on the average height of binary trees[END_REF][START_REF] Gutjahr | The asymptotic contour process of a binary tree is a Brownian excursion[END_REF][START_REF] Drmota | Distribution of the height of leaves of rooted trees[END_REF][START_REF] Gittenberger | On the contour of random trees[END_REF]. Here a similar limit theorem holds: With Xn (t) = Tn (tn)/ √ n we have (see [START_REF] Gittenberger | On the contour of random trees[END_REF])

Xn ϕ 0 ϕ(τ) t t ≥ 0 w -→ 2 σ W (t)t ≥ 0 .
In addition, in [START_REF] Gittenberger | On the contour of random trees[END_REF] the tightness estimate

P{| Xn (s) -Xn (t)| ≥ ε} ≤ C 1 ε 4 |s -t| exp -D ε |s -t|
for some positive constants C and D was shown. This can be used to derive moment estimates like in Lemma 5 and then one proceeds as in the previous section to re-derive Flajolet and Odlyzko's [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF] result on the moments of the height. Finally, we want to mention that it is also possible to obtain the moments of the height of a random mapping (this was done by Flajolet and Odlyzko [START_REF] Flajolet | Random mapping statistics[END_REF]) by our method. One has to use the weak limit theorem by Aldous and Pitman [START_REF] Aldous | Brownian bridge asymptotics for random mappings[END_REF] and derive a tightness estimate in a similar fashion as has been done in [START_REF] Drmota | Strata of random mappings-a combinatorial approach[END_REF].

Theorem 5 .

 5 Let L (d) n (k) denote the number of nodes with degree d in layer k in a random tree of total progeny n. Furthermore, set for any t ≥ 0 l = ϕ d-1 τ d-1 /ϕ(τ).

Theorem 8 .

 8 Suppose that there exists a minimal positive solution τ < R of tϕ ′ (t) = ϕ(t). Then

This research has been supported by the Austrian Science Foundation FWF, grant P16053.

1365-8050


Vincent Puyhaubert

Generating functions and the satisfiability threshold

Keywords: First moment method, exponential generating functions, saddle-point bounds

The 3-SAT problem consists in determining if a boolean formula with 3 literals per clause is satisfiable. When the ratio between the number of clauses and the number of variables increases, a threshold phenomenon is observed: the probability of satisfiability appears in simulations to decrease sharply from 1 to 0 in the neighbourghood of a threshold value, conjectured to be close to 4.25. Although the threshold has been proved to exist for the 2-SAT formulae and for closely related problems like 3-XORSAT, there is still no precise mathematical characterization of the threshold phenomena involved in the 3-SAT problem.

Recent works have provided so far upper and lower bounds for the threshold's potential location. We present here a unified approach to upper bounds that is based on urn models, generating functions, and saddle-point bounds. No new upper bound is presented here but instead, we show that several existing results (with long proofs) can be organized in a simpler and uniform manner.

Introduction

We consider boolean formulae over a set of variables x 1 , . . . , x n (where the x j range over {0, 1} or, equivalently, {true, false}). A literal is either a variable x j or a negated variable ¬x j . It is known that each boolean formula admits a conjunctive normal form, being a conjunction of clauses, themselves disjunctions of literals. A 3-SAT formula is then such a formula with exactly 3 literals per clause. A typical formula is then for example:

Φ = (x 1 ∨ ¬x 2 ∨ x 4 ) ∧ (¬x 2 ∨ ¬x 3 ∨ x 5 ) ∧ (x 1 ∨ ¬x 4 ∨ ¬x 5 ) ∧ (x 3 ∨ ¬x 4 ∨ ¬x 5 ).
We will choose the standard probabilistic model where each clause is composed of a set of three literals composed of distinct variables. There are then 8 n 3 distinct clauses and (8 n 3 ) m formulae with m clauses. The quantities n, m are the fundamental parameters of the model. From previous studies, we know that the "interesting" region is when n and m are linearly related m = rn. (Alternative models have occasionally been used for convenience in calculations, for example, the three literals may be ordered and not necessarily distinct so that there would be 8n 3 clauses. All such models are easily proved to be equivalent with respect to the asymptotic probability of satisfiability). In Figure 1, taken from Ludovic Meunier's master's thesis [START_REF] Meunier | Étude des transitions de phases en K-satisfaisabilité[END_REF], a phase transition phenomenon can be observed regarding the satisfiability of these formulae when they are drawn at random. As the ratio r = m/n of the number m of clauses to the number n of variables increases, the probability of satisfiability drops abruptly from nearly 1 to nearly 0. From these experiments, it is believed that there exists a critical value r 3 such that for any ε > 0, the probability of satisfiability tends to 1 for r < r 3 -ε (as m and n tend to infinity), and tends to 0 for r > r 3 + ε. Experiments suggest for r 3 the value 4.25 ± 0.05. However, so far, only successive upper and lower bounds on the threshold's potential location have been obtained. The table below lists the bounds successively established for the 3-SAT threshold. The bounds marked with a star admit an extension to k-SAT for any k. A survey by Olivier Dubois explains the techniques used to obtain them [START_REF] Dubois | Upper bounds on the satisfiability threshold[END_REF]. For the lower bounds, one can refer to the surveys by Franco [START_REF] Franco | Results related to threshold phenomena research in satisfiability: lower bounds[END_REF] and Achlioptas [START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF].

Lower bounds for 3-SAT threshold

Upper bounds for 3-SAT threshold 2.9 * Chao and Franco (1986[START_REF] Chao | Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem[END_REF] Apart from these works, Friedgut [START_REF] Friedgut | Sharp thresholds of graph properties, and the k-sat problem[END_REF] also proved that there exists a sequence γ n such that for any ε > 0, if m/n < γ n -ε then, the probability of satisfiability tends to 1 as m and n increase while it tends to 0 if m/n > γ n + ε. But it has not been proved that the sequence γ n converges to some limit value γ, that would then be equal to the threshold r 3 .

The aim of the present paper is to present some of the most significant upper bounds on the satisfiability threshold and organize them within a unified framework. We will specifically focus on enumerative proofs, based on generating functions.

Expectation of the number of solutions

The first bound for the 3-SAT threshold has been obtained by several authors as a direct application of the first moment method to the random variable giving the number of solutions of a random formula. Under an enumerative perspective, it can be regarded as a direct application of the following simple remark: since positive integer are ≥ 1, one has the inequality:

|{ Φ satisfiable }| ≤ |{ (Φ, S) such that Φ is satisfied by S }| (1)
where |E| denotes the cardinality of the set E. There, S represents an assignment of the n variables to values in {0, 1}. Let C = ±x i ∨ ±x j ∨ ±x k be a clause and fix some assignment C (we identify negation ¬ with the minus sign). There is only one way to choose the signs of the three literals in order to have the value of C be false under S: each literal must have the opposite sign of its assignment. Then, there are 7 ways to choose the signs in order to render C true. The number of clauses satisfied by any given S is then 7 n 3 . Since S is a solution of a 3-SAT formula Φ iff all clauses of Φ are satisfied by S, for any assignment, there are exactly (7 n

3 ) m formulas with m clauses which admit S as a solution. The cardinality of the pairs (Φ, S) such that S is a solution of Φ is then given by 2 n (7 n 3 ) m . Dividing each term of (1) by the total number of formulae (8 n

3 ) m gives (with r = m/n):

Pr ( Φ satisfiable ) ≤ 2 7 8 r n . (2)
For r > ln(2)/ ln(8/7) ≈ 5.191, the right side of (2) tends to 0 as n tends to infinity, and so does the probability of satisfiability. This gives the first upper bound obtained by Franco and Paull as early as 1983.

This argument can easily be extended to the problem k-SAT for any k. For any fixed assignment, the number of clauses it satisfies which are disjunctions of k literals is given this time by

(2 k -1) n k . The number of satisfied formulae is hence (2 k -1) n k m and since the total number of formulae is 2 k n k m , one has Pr ( Φ k-SAT satisfiable ) ≤ 2 (2 k -1) 2 k r n . (3)
The probability of satisfiability of k-SAT formulae tends to 0 when r >ln(2)/ ln(1 -2 -k ) and the following proposition holds Proposition 1 (Franco and Paull [START_REF] Franco | Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem[END_REF]) Let m, n be integers and Ω m,n the set of k-SAT formulae with m clauses constructed over n variables. Let m, n → ∞, while m/n ≥ r. Then, for any r >ln(2)/ ln(1-2 -k ), the expectation of the number of solutions of a random formula tends to 0 and hence

Pr{φ ∈ Ω m,n is satisfiable} -→ 0.
For k = 3, the bound is 5.191.

Note that this majorization of the threshold also holds for k = 2, but the valueln(2)/ ln(3/4) ≈ 2.4 is appreciably greater than the exact value of the 2-SAT threshold, which has been proved to be 1. It also suggests 2 k ln(2) as an approximate value of the threshold for large k of the potential threshold location.

Prime implicants

In the previous section, we have bounded the number of satisfiable formulae by the number of formulasolution pairs. Since a satisfiable formula may have from 1 to almost 2 n solutions, the upper bound obtained may be very coarse. The next idea is to group some of the solutions which look very close to each other, and enumerate only these groups for each formula. In this way, it may be possible to get an improved upper bound on the satisfiability threshold.

This leads to the idea of using partial assignments and prime implicants, first introduced in this context by Olivier Dubois and Yacine Boufkhad [START_REF] Boufkhad | Length of prime implicants and number of solutions of random CNF formulae[END_REF]. A partial assignment A is simply an assignment to a subset of the n variables (possibly all, so that complete assignment are also considered partial assignments). Let us say that A satisfies a formula Φ iff all complete assignments A ′ extending A are solutions of Φ. A necessary and sufficient condition for this is that in each clause of Φ, at least one of the three literals is true under A. Note that this implies that at least one variable is assigned. If there are i missing variables in a partial assignment A, then A "groups" 2 i solutions together.

A natural order may be placed on partial assignments. We say that A is smaller than B if we can remove some assigned variables from B to get A. A prime implicant of a formula φ is then defined as a partial assignment which is minimal with respect to this order. Any satisfiable formula has then at least one prime implicant since it has at least one solution and the set of partial assignments is then non empty. As in the previous section, we get from there the inequality (see (1)):

|{ Φ satisfiable }| ≤ |{ (Φ, I) such that I is a prime implicant of Φ }| . (4)
Note that the sets of solutions grouped together by two different partial assignments are not necessarily disjoint and some formulae may even have more prime implicants than solutions. But in fact, on average, the number of prime implicants of a random formula appears to be smaller by an exponential factor than the number of solutions.

At this point, we start an original re-derivation of the upper bound value 4.883 obtained by O. Dubois and Y. Boufkhad for the 3-SAT threshold, with the help of generating functions, which provides a much shorter proof of their estimate.

Let us consider the partial assignment I which assigns all variables x 1 , . . . , x ℓ to 0. Then, all clauses in a formula Φ that admits I as a prime implicant must contain at least one literal satisfied by I. Any such clause is hence of the form ¬x i ∨ a ∨ b with 1 ≤ i ≤ ℓ. Let A n,ℓ be the set of such clauses and α n,ℓ their number. Since the complement of A n,ℓ is the set of clauses which do not contain any literal

(¬x i ) i∈[[ 1 ; ℓ ]] , it follows α n,ℓ = 8 n 3 - ℓ 3 + 2 ℓ 2 (n -ℓ) + 4ℓ n -ℓ 2 + 8 n -ℓ 3 .
Recall that I has to be minimal with respect to the order defined earlier. Remove the variable x i from the set of assigned variables. Then at least one clause in Φ no longer contains a positive literal. Hence Φ must contains a clause of the form ¬x i ∨ a ∨ b with a and b either of the form

(x i ) i∈[[ 1 ; ℓ ]] or (±x i ) i∈[[ ℓ+1 ; n ]] .
Let B n,ℓ,i be the set of these clauses and β n,ℓ,i their number. It is easy to see that these sets are mutually disjoint and have the same cardinality

β n,ℓ,i = β n,ℓ = ℓ -1 2 + 2(ℓ -1)(n -ℓ) + 4 n -ℓ 2 .
Finally, to build a formula which admits I as a prime implicant, one must draw m elements in the set A n,ℓ so that in the subsets

(B n,ℓ,i ) i∈[[ 1 ; ℓ ]] ,
at least one element is taken. The number of such draws is then the number I m,n,ℓ whose generating function is given by

I n,ℓ (z) = ∑ m≥0 I n,ℓ,m z m m! = e z (α n,ℓ -ℓβ n,ℓ ) e z β n,ℓ -1 ℓ . (5)
The proof of this statement is given in the first part of the appendix. It is based on generating functions and the enumeration of throws in urns. Now, it is clear that for any other partial assignment of ℓ variables, the number of formulae of length m for which it is a prime implicant is the same as the one where the ℓ first variables are assigned to 0 and thus, it only depends on m, n and ℓ. Finally, since there are n ℓ 2 ℓ possible partial assignments of ℓ variables, the total number of pairs (Φ, I) such that I is a prime implicant for Φ is given by:

|{ (Φ, I prime implicant ) }| = n ∑ ℓ=1 n ℓ 2 ℓ I m,n,ℓ . (6)
The next step depends on the following general remark: if ( f k ) is a sequence of non negative reals and f (z) = ∑ f k z k then for all s > 0 within the domain of convergence of f (z):

f k ≤ min s f (s) s k .
This is a very classical majorization called the saddle-point bound (the minimum of the function s → f (s)s -k is called the saddle point and the shape of the complex function f (s)s -k in its neighbourhood looks like a horse's saddle). The majorization may seem coarse since

f (s)s -k = f 0 s -k + • • • + f k + f k+1 s + • • • ,
but in many cases it gives the exact exponential rate of growth of the coefficient f k knowing the generating function f (z).

From now on, we set ℓ = αn, m = rn and make use of the majorizations

α n,ℓ -ℓβ n,ℓ ≤ 1 3 ℓ 2 (3n -ℓ) and β n,ℓ ≤ 1 2 (2n -ℓ) 2 .
From the previous remark, it follows that for any u α

I rn,n,αn ≤ (rn)! n 2m e α 2 (1-α/3)u α e 2(1-α/2) 2 u α -1 α u -r α n .
The same remark proves that for any integer s, one has 1 s! ≤ e s s s . Combining this inequality (for the denominator) with Stirling's formula (for the numerator) ensures that there exists a constant C such that, for each integer n and each α such that αn is an integer, one has

n αn ≤ C √ n α α (1 -α) 1-α -n . (7)
Naturally, stronger asymptotic estimates are possible, e.g. n αn ∼ (2πnα(1 -α)) -1/2 α α (1 -α) 1-α -n follows obviously from three applications of Stirling formula. However, equation ( 7) wholy suffices for our purposes while making subsequent argumentations simpler.

Finally, since (rn)!n 2rn (8( n 3 )) rn ∼ √ 2πre 3r n 1/2 3r 4e rn , ( 4) and [START_REF] Chao | Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem[END_REF] give

Pr ( Φ satisfiable ) ≤ C ′ n ∑ α∈{ 1 n , 2 n ,..., n-1 n ,1} f r (α, δ α ) n (8) with f r (α, δ α ) = 3r 4e r 2 α α α (1-α) 1-α e α 2 (1-α/3) 2(1-α/2) 2 δ α e δ α -1 α δ -r α 2 r (1 -α/2) 2r
and where δ α can be any strictly positive real. In order to get the best majorization, δ α has to minimize the expression between parentheses. If 0 < α < r, this expression has a unique minimum δ α given by

α 2 (1 -α/3) 2(1 -α/2) 2 δ α + α δ α 1 -e -δ α = r.
Assume that r > 1. Then one gets

Pr ( Φ satisfiable ) ≤ C ′ n 2 max α∈]0,1] g r (α) n with g r (α) = f r (α, δ α ).
Any real r > 1 such that the maximum of g r over ]0, 1] is strictly smaller than 1 is hence an upper bound on the satisfiability threshold. The value r = 4.883 is then the best value computed with Maple which has this property (details are given in the second part of appendix). [START_REF] Boufkhad | Length of prime implicants and number of solutions of random CNF formulae[END_REF]) Let m, n be integers and Ω m,n the set of 3-SAT formulae with m clauses constructed over n variables. Let m, n → ∞, while m/n ≥ r. Then, for any r > 4.883, the expectation of the number of prime implicants of a random formula tends to 0 and Pr{φ ∈ Ω m,n is satisfiable} -→ 0.

Proposition 2 (Dubois and Boufkhad

The same analysis can easily be extended to k-SAT for any integer k.

Negatively prime solutions

The next idea is to introduce a partial order on the set of solutions. Define B to be an assignment smaller than A if one can change the values of some of B's variables from 0 to 1 to get A. We could envisage to enumerate only pairs (Φ, S) where S is a maximal solution with respect to this order; however, it is very difficult to find for any given assignment a simple characterization of formulae for which it is a maximal solution. In order to remedy this situation, Olivier Dubois and Yacine Boufkhad introduced a weaker definition of local maximal solution (also called negatively prime solution or NPSs). This is a solution for which changing the value of any variable from 0 to 1 no longer gives a solution. This amounts to considering solutions which do not admit a greater solution that differs in exactly one variable. Once more, there holds the inequality

|{ Φ satisfiable }| ≤ |{ (Φ, S) such that S is an NPS of Φ }| (9)
and the probability of satisfiability is smaller than the expectation of the number of NPSs. What follows now is a new calculation of this expectation.

Let A be an assignment setting ℓ variables to the value 0 and Φ a formula for which A is an NPS . Then, all clauses of Φ must belong to the set A n of all 7 n 3 clauses satisfied by A (as seen in Section 2). Now, if any variable x i assigned to 0 is changed to 1, there must be at least one clause in Φ that is no longer satisfied by this new assignment: at least one clause must be thus of the form ¬x i ∨ a ∨ b, where a and b are false under A. If we denote by C x i this last set of clauses (for each variable assigned to 0), then all these sets have the same number n-1 2 of elements and are mutually disjoint. As in the previous section, since there are n ℓ solutions with ℓ variables assigned to 0, we get:

|{ (Φ, A NPS ) }| = n ∑ ℓ=0 n ℓ m! [z m ]e z (7( n 3 )-ℓ( n-1 2 )) e z ( n-1 2 ) -1 ℓ where [z m ] f (z) represents the coefficient f m in the Taylor expansion f (z) = ∑ f i z i .
The linearity of coefficient extraction gives a closed-form expression:

|{ (Φ, A NPS ) }| = m! [z m ]e z 7( n 3 ) 2 -e -z ( n-1 2 ) n . ( 10
)
The same use of saddle-bound as in the previous section, the same majorization provided by Stirling's formula, and the change of variable δ = z n-1 2 provide that, for any δ > 0 with m = rn,

Pr(Φ satisfiable ) ≤ C √ 2πrn 3r 8e r e 7 3 δ 2 -e -δ δ r n . ( 11
)
This expression is minimized by δ 7 3 -1 2e δ -1 = r and, with such a δ, is strictly smaller than 1 as soon as r > 4.643. Hence Proposition 3 (Dubois and Boufkhad [START_REF] Dubois | A general upper bound for the satisfiability threshold of random r-SAT formulae[END_REF]) Let m, n be integers and Ω m,n the set of 3-SAT formulae with m clauses constructed over n variables. Let m, n → ∞, while m/n ≥ r. Then, for any r > 4.643, the expectation of the number of NPSs of a random formula tends to 0 and

Pr{φ ∈ Ω m,n is satisfiable} -→ 0.
Once more, this upper bound can be extended to k-SAT for any k. For any assignment giving the value 0 to ℓ variables, the number of satisfied clauses which are disjunction of k literals is this time (2 k -1) n k . Once more, for all variable x i assigned to 0, define the set C x i of clauses which forbid the flip of x i from 0 to 1. Then, all these sets are mutually disjoint and have the same cardinality n-1 k-1 . The same arguments then provide the exact formula

|{ (Φ k-SAT, A NPS ) }| = n ∑ ℓ=0 n ℓ m! [z m ]e z ((2 k -1)( n k )-ℓ( n-1 k-1 )) e z ( n-1 k-1 ) -1 ℓ (12)
which gives the general majorization for any δ > 0, considering k-SAT formulae of length m = rn,

Pr(Φ k-SAT satisfiable ) ≤ C √ 2πrn   kr 2 k e r e 2 k -1 k δ 2 -e -δ δ r   n . (13)
With δ 2 k -1 k -1 2e δ -1 = r, one determines that the probability of satisfiability of k-SAT formulae of length m = rn tends to 0 as soon as r > 10.217 for k = 4 and r > 43.508 for k = 6 for instance. This general upper bound has first been obtained by Olivier Dubois and is still so far the best one for general k. However, the initial proof took 25 pages where ours only needs about 2.

Appendix

Throws into urns and generating functions

Let us consider a general problem. Let M 1 , . . . , M p be subsets of N. One has a collection of p urns and wants to throw in these urns m distinguishable balls (say by integer labels 1, 2, 3, . . .), such that in the end, the number of balls in urn i is in M i . For instance, if M 1 = {0, 1, 2} and M 2 = {2, 3, . . .}, one want to throw at most two balls in the first urn and at least two balls in the second one. The problem is to enumerate the number of such throws.

Let F m be this number. Then clearly, one has

F m = ∑ n 1 +•••+n p =m m n 1 ; • • • ; n p [[n 1 ∈ M 1 ]] × • • • × [[n p ∈ M p ]] (14)
where [[P ]] equals 1 if P is true and equals 0 otherwise. The binomial coefficient enumerates all ways to put n 1 balls in urn 1, n 2 balls in urn 2 and so on. The product is then equal to 1 if and only if all conditions concerning the final number of balls in each urn are satisfied. Introduce the exponential generating function of the sequence (F m ). Then, [START_REF] Frieze | Analysis of two simple heuristics on a random instance of k-SAT[END_REF] immediately implies

F(z) = ∑ m∈N F m z m m! = ∑ i∈M 1 z i i! × • • • × ∑ i∈M p z i i! . ( 15
)
For instance, the generating function of the example above is F(z) = ( z 2 2 + z + 1)(e zz -1). Let us now consider a slightly more complex problem. We now have p subsets of urns, say E 1 , . . . , E p of cardinality e 1 , . . . , e p , and p subsets of N M 1 , . . . , M p . This time, we want to throw m distinguishable balls in all these urns such that in the end, for any i, the total number of balls in the subset E i of urns is an element of M i . The formula [START_REF] Frieze | Analysis of two simple heuristics on a random instance of k-SAT[END_REF] now becomes

F m = ∑ n 1 +•••+n p =m m n 1 ; • • • ; n p [[n 1 ∈ M 1 ]] (e 1 ) n 1 • • • [[n p ∈ E p ]] (e p ) n p . ( 16
)
since there is now (e i ) n i ways to throw n i balls in the subset E i of urns, and the translation of this formula into generating function gives

F(z) = ∑ m∈N F m z m m! = ∑ i∈M 1 (e 1 z) i i! × • • • × ∑ i∈M p (e p z) i i! . ( 17
)
In section 3, we had to pick elements in one set A n,ℓ , so that in ℓ subsets B n,ℓ,i , at least 1 element is picked. Let Ãn,ℓ = A n,ℓ -(∪ 1≤i≤ℓ B n,ℓ,i ). This is equivalent to picking any number of elements in Ãn,ℓ and at least one in each of the B n,ℓ,i .

"Replace" now each clause by an urn. Picking m clauses with replacement to construct a formula is then equivalent to throwing m distinguishable balls in the set of urns. The enumeration of such draws can thus be regarded as an urn problem just defined, where we dispose of ℓ + 1 sets of urns. The first set contains αn,ℓ = α n,ℓ -ℓβ n,ℓ urns and we may throw any number of balls in it (hence M 1 = N). The other sets each contain β nℓ urns and we must throw at least one ball in one urn of the set (hence

M 2 = • • • = M ℓ+1 = N * ).
The equation ( 17) finally gives the desired result.

Maple computations

In this section, we prove with the help of Maple that for r = 4.883, the maximum of g r defined in section 3 is strictly smaller than 1. The idea is to get a coarse majorization of g ′ r and then to ask Maple to evaluate g r at sufficiently many points x 0 < • • • < x p . With the mean value theorem, the condition

1 -max i∈[[ 0 ; p ]] {g r (x i )} > ||g ′ r || 2 max i∈[[ 0 ; p-1 ]] |x i+1 -x i | (18)
ensures that for any t ∈ / {x 0 , . . . , x p }, it also holds that g r (t) < 1. The purpose of this section is hence to replace many pages of analysis by Dubois and Boufkhad by a combination of straightforward inequalities and trivial computation.

A minor difficulty arises from the fact that the function α → 2 α α α (1-α) 1-α has infinite derivatives at 0 and 1. Hence, a rough majorization of g r on intervals of the form ]0, ε] and [1 -η, 1] must be obtained first. Monotonicity properties : The function g r can be written as a product of one constant 3r 2e r and two functions which are:

f 1 : α → 2 α α α (1 -α) 1-α 1 - α 2 2r f 2 : α → exp α 2 (1 -α/3) 2(1 -α/2) 2 δ α + α ln e δ α -1 -r ln δ α .
First of all, one can prove that δ α and f 2 are both monotonic functions. Let us define

h(x, y) = x 2 (1 -x/3) 2(1 -x/2) 2 y + x y 1 -e -y .
Since h(α, δ α ) = r, differentiating this expression with respect to α yields

∂h ∂x (α, δ α ) + δ ′ α ∂h ∂y (α, δ α ) = 0 ⇒ δ ′ α = - ∂h ∂x ∂h ∂y (α, δ α ).
It now easy to verify that both ∂h ∂x and ∂h ∂y are positive function on [0, 1]×]0, +∞[ and hence, δ α is a decreasing function of α. Concerning the function f 2 , the condition h(α, δ α ) = r also implies

f ′ 2 (α) = α(12 -6α + α 2 ) 3(2 -α) 3 δ α + ln(e δ α -1) f 2 (α).
The function α → δ α being decreasing, for any α, ln(e δ α -1) ≥ ln(e δ 1 -1) ≈ 1.8017 > 0. Hence, f ′ 2 is positive and f 2 is an increasing function of α.

Finally, the function f 1 satisfies

f ′ 1 (α) = ln(2) -ln(α) + ln(1 -α) - 2r 2 -α f 1 (α).
The expression between parentheses is smaller than ln(2)ln(α) + ln(1 -α)r, which is negative as soon as α > 2 e r +2 ∼ 0.0149. The function f 1 is thus decreasing on [0.015, 1]. Majorization of g r on ]0, 0.897] and [0.957, 1]: First of all, we make use of the majorization

2 α α α (1 -α) 1-α 1 - α 2 2r ≤ 3 ∀ α ∈ [0, 1]
which implies that for any α ∈]0, 0.414], g r (α) ≤ 3 3r By subdividing [0.015, 1] into many small intervals, it is shown with this majorization that g r is smaller than 1 on both intervals ]0, 0.897] and [0.957, 1]. It is easy to see that both ∂h ∂x and ∂h ∂y are positive increasing functions of x and y so their respective greatest and lowest values are ∂h ∂x (0.957, δ 0.897 ) and ∂h ∂y (0.897, δ 0.957 ). To majorize ∂ f r ∂α and ∂ f r ∂δ α , we introduce a r such that f r = exp(a r ). Then ∂y . The derivatives of a r are simple functions, and finally, a coarse majorization of f r , ∂a r ∂x and ∂a r ∂x gives the bound:

Majorization of g

for any α ∈ [0.897, 0.957], g ′ r (α) ≤ 60.

Numerical evaluations:

We set r = 4.883. We got Maple to compute the greatest value of g r with an accuracy of 15 digits for points in the interval [0.897, 0.957] at distance at most 0.6 • 10 -7 of each other (10 6 values). The greatest value returned was 1 -0.2721 • 10 -5 . Hence, the condition ( 18) is verified and the value 4.883 is proved to be a valid upper bound of the satisfiability threshold.

  1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Fig. 1 :

 1 Fig. 1: Ratio of satisfiable formulae wrt the parameter m/n.

2e r f 2

 2 (0.414) ≈ 0.992. Then we use the fact that f 1 is decreasing on [0.015, 1] to conclude that on any interval [a, b] with a > 0.015, for any α ∈ [a, b], g r (α) ≤ 3r 2e r f 1 (a) f 2 (b).

  ′ r on [0.897, 0.957]: For any α ∈ [0.897, 0.957], one has δ 0.957 ≤ δ α ≤ δ 0.897 . Differentiating g r with respect to α gives g ′ r (α) =

  a r (α, δ α ) = C ′′ + α ln(2) -α ln(α) -(1 -α) ln(1 -α) + α 2 (1 -α/3) 2(1 -α/2) 2 δ α +α ln(e δ α -1)r ln(δ α ) + 2r ln(1 -α/2),and we have both ∂ f r ∂x = f r ∂a r ∂x and ∂ f r ∂y = f r ∂a r

Acknowledgements

I want to thank Olivier Dubois for all the time he took to explain his articles to me, and Philippe Flajolet for pointing to generating functions as a useful tool for enumeration in threshold phenomena. Thanks also to an anonymous referee for many constructive and encouraging remarks.


Alois Panholzer
email: alois.panholzer@tuwien.ac.at

Helmut Prodinger
email: helmut@maths.wits.ac.za

Analysis of some statistics for increasing tree families

Keywords: increasing trees, Steiner-distance, ancestor-tree size

This paper deals with statistics concerning distances between randomly chosen nodes in varieties of increasing trees. Increasing trees are labelled rooted trees where labels along any branch from the root go in increasing order. Many important tree families that have applications in computer science or are used as probabilistic models in various applications, like recursive trees, heap-ordered trees or binary increasing trees (isomorphic to binary search trees) are members of this variety of trees. We consider the parameters depth of a randomly chosen node, distance between two randomly chosen nodes, and the generalisations where p nodes are randomly chosen: the size of the ancestor-tree of these selected nodes and the size of the smallest subtree generated by these nodes, also called Steiner distance. Under the restriction that the node-degrees are bounded, we can prove that all these parameters converge in law to the Normal distribution. This extends results obtained earlier for binary search trees and heap-ordered trees to a much larger class of structures.

Introduction

In this paper we consider families of increasing trees. Increasing trees as defined in [START_REF] Bergeron | Varieties of Increasing Trees[END_REF] are labelled trees (the nodes of a tree of size n are labelled by distinct integers of the set {1, . . . , n}), such that each sequence of labels along any branch starting at the root is increasing. As the underlying tree model, we use the † Part of this work was done during the first author's visit to the John Knopfmacher Centre for Applicable Analysis and Number Theory at the University of the Witwatersrand, Johannesburg, South Africa. 1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France so called simply generated trees, compare [START_REF] Meir | On the altitude of nodes in random trees[END_REF]. They are essentially the same as Galton-Watson trees, obtained as the family tree of a Galton-Watson branching process conditioned on a given total size, see e. g., [START_REF] Aldous | The continuum random tree II: an overview, Stochastic analysis[END_REF]. Additionally, they are equipped with increasing labellings. We will thus speak about simple families of increasing trees. A thorough study of families (=varieties) of increasing trees was conducted in [START_REF] Bergeron | Varieties of Increasing Trees[END_REF].

A class T of a simple family of increasing trees can be defined in the following way. A sequence of non-negative numbers (ϕ k ) k≥0 with ϕ 0 > 0 is used to define the weight w(T ) of any planted plane tree T by w(T ) = ∏ v ϕ d (v) , where v ranges over all vertices of T and d(v) is the out-degree of v. Further, λ(T ) denotes the number of different increasing labellings of the tree T . Then the family T consists of all trees T together with their weights w(T ) and the various increasing labellings λ(T ).

For a given integer sequence (ϕ k ) k≥0 , the quantities

T n := ∑ |T |=n w(T ) • λ(T ),
are counting the number of trees of size n in T , where |T | denotes the size (=number of nodes) of the tree T .

Further we define by

ϕ(t) = ∑ k≥0 ϕ k t k , (1)
the degree generating function ϕ(t), which contains all the information required for analysing the tree parameters that we consider in this paper.

As it is natural in enumeration problems related to labelled structures, we use the exponential generating function

T (z) := ∑ n≥0 T n z n n! . ( 2
)
It follows then from the recursive way in which these trees are generated that

T ′ (z) = ∑ n≥1 T n z n-1 (n -1)! = ∑ n≥1 ∑ k≥0 ϕ k ∑ n 1 +•••+n k =n-1 ∑ T : |T |=n, d(root)=k, |S 1 |=n 1 ,...,|S k |=n k ( n-1 n 1 ,...,n k )w(S1)λ(S1)•••w(Sk)λ(Sk)z n-1 (n-1)! = ∑ k≥0 ϕ k T k (z) = ϕ T (z) ,
where the degree of the root is k and the subtrees S 1 , . . . , S k have sizes n 1 , . . . , n k , respectively. Thus, for simple families of increasing trees with degree generating function ϕ(t), the (exponential) generating function T (z) satisfies the autonomous first order differential equation

T ′ (z) = ϕ T (z) , T (0) = 0. ( 3
)
As an example we list in Figure 1 all planar unary-binary increasing trees of size 4. These trees are described via the degree generating function ϕ(t) = 1 + t + t 2 .

In [START_REF] Bergeron | Varieties of Increasing Trees[END_REF], an asymptotic study of many parameters related to simple families of increasing trees can be found. These results are obtained by means of a generating functions approach and naturally depend on the degree generating function ϕ(t).

We want to give a few examples as an illustration that simple families of increasing trees are not an obscure construction but occur rather naturally.

We begin with the so called recursive trees, which are the family of non-planar increasing trees where all node degrees ≥ 0 are allowed. They are described by the degree generating function ϕ(t) = exp(t). This model is used among other things to describe the spread of epidemics, for pyramid schemes or as a basis of Burge's sorting method (see e. g., [START_REF] Mahmoud | A Survey of Recursive Trees[END_REF]).

Another family of trees are the so called heap ordered trees (also known as plane recursive trees), which are planar increasing trees such that all node degrees are allowed. They are described by the degree generating function ϕ(t) = 1 1-t . They can be used for pyramid schemes based on the principle "success breeds success" (see also [START_REF] Mahmoud | A Survey of Recursive Trees[END_REF]).

Finally we want to mention the so called binary increasing trees, which are labelled unary-binary trees with one sort of leaves and one sort of binary nodes, but two sorts of unary nodes (left branching nodes and right branching nodes); thus they are described by the degree generating function ϕ(t) = (1 + t) 2 . They can be used as a data structure to represent mergeable priority queues, with algorithms that can be precisely analysed (see [START_REF] Bergeron | Varieties of Increasing Trees[END_REF]). This tree model is also isomorphic to the model of standard binary search trees (and thus to the Quicksort algorithm, see e. g., [START_REF] Ph | An Introduction to the Analysis of Algorithms[END_REF]). Hence when analysing structural parameters, we can either do it in the binary search tree model or in the binary increasing tree model.

For the last-mentioned model of binary search trees, two tree parameters are analysed in [START_REF] Panholzer | Spanning tree size in random binary search trees[END_REF], which extend the quantities depth of a random node and distance between two random nodes. The depth of a node v is here defined as the number of nodes lying on the unique path from the root to v. The natural extension size of the ancestor-tree of p chosen nodes v 1 , . . . , v p measures the size of the tree spanned by the root and v 1 , . . . , v p and therefore counts the number of nodes that are lying on at least one direct path from the root to v i for 1 ≤ i ≤ p. For binary search trees this parameter is of interest when analysing the average behaviour of the Multiple Quickselect algorithm (see e. g. [START_REF] Prodinger | Multiple Quickselect -Hoare's Find algorithm for several elements[END_REF]), which is used to find arbitrary p-order statistics in a data file of length n.

The node distance between v 1 and v 2 is defined as the number of nodes lying on the direct path from v 1 to v 2 . A study of the distance between nodes is of interest for various tree families. E. g., the distance between two specified nodes appears in the analysis of the costs of finger search operations in search tree structures (see [START_REF] Devroye | Distances and finger search in random binary search trees[END_REF]). Moreover, heap ordered trees (they are a special instance of the so called Albert-Barabási-model for scale-free networks, see [START_REF] Bollobás | Mathematical results on scale-free random graphs[END_REF])) and recursive trees (see [START_REF] Van Der Hofstad | On the Covariance of the Level Sizes in Random Recursive Trees[END_REF]) are used to model the growth of the world-wide-web. Thus in this context the distance between randomly chosen nodes in heap ordered trees resp. recursive trees is of interest when analysing the "hopcount" problem of the internet, which asks for the number of hops (= traversed routers) along the shortest path between two arbitrary nodes in the internet.

The natural extension for the parameter distance between two nodes is the spanning subtree size of p chosen nodes v 1 , . . . , v p and thus counts the number of nodes that lie on at least one direct path from v i to v j for 1 ≤ i ≤ j ≤ p. In the literature, this parameter is also known as the Steiner distance between these p nodes (see e. g., [START_REF] Dankelmann | The Average Steiner Distance of a Graph[END_REF]). Such measures are used for analyzing transportation networks and multiprocessor computer networks.

Our previous paper [START_REF] Panholzer | Spanning tree size in random binary search trees[END_REF] contains the following results for the binary search tree model: Under the assumption that all n p possibilities of selecting p nodes in a tree of size n are equally likely, the distribution of the Steiner distance of p chosen nodes as well as the distribution of the size of the ancestor-tree of p chosen nodes is asymptotically Gaussian for n → ∞ and fixed p; mean and variance are asymptotically 2p log n.

See Figure 2 for a comparison of both parameters considered here: ancestor-tree size and Steinerdistance for a given increasing tree. (a) Ancestor-tree of the three marked nodes {4, 9, 11} is of size 7. The intention of this work is to generalise the limiting distribution results for the Steiner distance and for the ancestor-tree size that were obtained for the special case of binary increasing trees in [START_REF] Panholzer | Spanning tree size in random binary search trees[END_REF], and for the case of heap ordered trees in [START_REF] Morris | On some parameters in heap ordered trees, Combinatorics[END_REF], to other members of the simple family of increasing trees. We will carry out this analysis for all simple increasing trees where the possible node degrees are bounded, and thus the degree generating function ϕ(t) = ϕ 0 + • • • + ϕ d t d is a polynomial of degree d ≥ 2. We will thus speak about the polynomial variety of increasing trees.

Important special cases are the d-ary increasing trees (ϕ(t) = (1 + t) d ) and the planar unary-binary increasing trees (ϕ(t) = 1 + t + t 2 ), whereas the above mentioned recursive trees and heap-ordered trees are not covered by this analysis. So, the results in [START_REF] Panholzer | The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees[END_REF] (recursive trees), [START_REF] Morris | On some parameters in heap ordered trees, Combinatorics[END_REF] (heap ordered trees) and in the present paper complement each other.

However, in principle one can also obtain results for tree classes with unbounded node-degrees (where ϕ(t) is not a polynomial) using the methods of this paper. This is technically more subtle and depends on whether one can describe the behaviour of T (z) near their dominant singularities (see Section 2).

Throughout this paper we will (for a given tree family) denote by X n,p the random variable counting the size of the ancestor tree of p randomly chosen nodes in a tree of size n and by Y n,p the random variable counting the Steiner distance of p randomly chosen nodes in a tree of size n. The main result concerning the limiting distribution of these parameters in a polynomial variety of increasing trees is then stated in the next two theorems. The distribution function of the standard normal distribution N (0, 1) is denoted by Φ(x).

Theorem 1. Given a polynomial variety of increasing trees with degree generating function

ϕ(t) = ϕ 0 + • • • + ϕ d t d with d ≥ 2, ϕ 0 > 0, ϕ d > 0 and ϕ k ≥ 0 for 0 < k < d.
The distribution of the random variable X n,p , which counts the size of the ancestor-tree of p randomly chosen nodes in a random tree of size n, is for fixed p ≥ 1 asymptotically Gaussian, where the convergence rate is of order

O 1 √ log n : sup x∈R P X n,p -E(X n,p ) V(X n,p ) ≤ x -Φ(x) = O 1 √ log n .
The expectation E n,p = E(X n,p ) and the variance V n,p = V(X n,p ) satisfy

E n,p = pd d -1 log n + c p + O 1 n 1 d-1 -ε , V n,p = pd d -1 log n + d p + O 1 n 1 d-1 -ε
, with constants c p resp. d p that are specified in Section 3.

Theorem 2. Given a polynomial variety of increasing trees with degree generating function

ϕ(t) = ϕ 0 + • • • + ϕ d t d with d ≥ 2, ϕ 0 > 0, ϕ d > 0 and ϕ k ≥ 0 for 0 < k < d. The distribution of
the random variable Y n,p , which counts the Steiner distance (and thus the spanning subtree size) of p randomly chosen nodes in a random tree of size n, is for fixed p ≥ 2 asymptotically Gaussian, where the convergence rate is of order O 1 √ log n :

sup x∈R P X n,p -E(X n,p ) V(X n,p ) ≤ x -Φ(x) = O 1 √ log n .
The expectation E n,p = E(Y n,p ) and the variance V n,p = V(Y n,p ) satisfy

E n,p = pd d -1 log n + cp + O 1 n 1 d-1 -ε , V n,p = pd d -1 log n + dp + O 1 n 1 d-1 -ε
, with constants cp resp. dp that are specified in Section 4.

Mathematical analysis of the parameters

Known results for the generating function T (z)

As the starting point in our analysis of the parameters X n,p and Y n,p , we will collect results from [START_REF] Bergeron | Varieties of Increasing Trees[END_REF] concerning the structure of the generating function T (z).

Theorem 3. [Bergeron et al.] The exponential generating function T (z) of a simple family of increasing trees defined by the degree function

ϕ(t) = ∑ k≥0 ϕ k t k , ϕ 0 > 0, ϕ k ≥ 0 is given implicitly by Z T (z) 0 dt ϕ(t) = z. ( 4
)
Depending on the degree function ϕ(t), periodicity phenomena can occur. If ϕ(t) is a function of t q for some q ≥ 2, such that ϕ(t) = ψ(t q ) for some power series ψ, one says that ϕ(t) is periodic and the maximum possible q is called the period (otherwise ϕ(t) is called aperiodic, q = 1). For a period q ≥ 2 one gets e. g., by applying the Lagrange inversion formula, that T (z) = zT * (z q ) for some power series T * . Thus non-zero coefficients T n can occur only if the congruence condition n ≡ 1 (mod q) is satisfied. For the asymptotic behaviour of the coefficients T n one can translate the behaviour of T (z) in the neighbourhood of the dominant singularities (singularities with smallest modulus) via singularity analysis (see [START_REF] Ph | Singularity Analysis of Generating Functions[END_REF]).

The next theorem describes the location of the dominant singularities.

Theorem 4. [Bergeron et al.] Given a polynomial degree function

ϕ(t) = ∑ 0≤k≤d ϕ k t k with ϕ 0 > 0, ϕ d > 0, ϕ k ≥ 0 for 0 < k < d. The dominant real positive singularity of the function T (z), solution of T ′ (z) = ϕ(T (z)), T (0) = 0, is then given by ρ = Z ∞ 0 dt ϕ(t) . ( 5
)
Furthermore, if ϕ(t) is non periodic, ρ is the only dominant singularity of T (z). If ϕ(t) has period q ≥ 2, then T (z) = zT * (z q ), where T * (t) has a unique dominant singularity at t = ρ q .

From this theorem it follows that T (z) is analytic in a domain larger than the disk of convergence if we slit at angles 2πm/q: it exists a ρ ′ > ρ, such that T (z) is analytic in the domain

D := {z ∈ C : |z| ≤ ρ ′ , z = re iφ with ρ ≤ r ≤ ρ ′ , φ = 2πm/q and 0 ≤ m < q}. ( 6
)
The next theorem describes the behaviour of T (z) near the dominant singularity ρ. For a polynomial degree generating function ϕ(t) = ∑ 0≤k≤d ϕ k t k of degree d we use throughout this paper the abbreviations

δ := 1 d -1 and η := ϕ d ρ δ δ . ( 7
)
Theorem 5. [Bergeron et al.] Let ϕ(t) = ϕ 0 + • • • + ϕ d t d with ϕ 0 > 0, ϕ d > 0, ϕ k ≥ 0 for 0 < k < d, be a polynomial degree function with degree d ≥ 2. Then in a complex neighbourhood of ρ, the solution T (z) is of the form T (z) = 1 ∆(z) H ∆(z) , where ∆(z) = η 1 - z ρ δ , (8)
and

H(t) = ∑ k≥0 h k t k is analytic at t = 0, with h 0 = 1.
Via singularity analysis one gets then in the aperiodic case immediately the asymptotic behaviour of the coefficients T n . If the degree generating functions ϕ(t) has period q ≥ 2 one has q dominant singularities, and their contributions have to be added. This leads to an extra factor q in the formula [START_REF] Hwang | On Convergence Rates in the Central Limit Theorems for Combinatorial Structures[END_REF] as stated in the next theorem.

Theorem 6. [Bergeron et al.] Let T be a polynomial variety associated with the degree generating function

ϕ(t) = ϕ 0 + • • • + ϕ d t d , ϕ 0 > 0, ϕ d > 0, ϕ k ≥ 0 for 0 < k < d.

The quantities T n of elements of T

with size n satisfy for d ≥ 2:

T n n! = q ηΓ(δ) ρ -n n -1+δ 1 + O n -2δ . (9)

Outline of the generating functions approach for X n,p and Y n,p

We will start now by giving a generating functions approach to obtain the results for the random variables X n,p and Y n,p stated in Theorem 1 and Theorem 2. To do this, we introduce the generating functions

G(z, u, v) = ∑ n≥0, p≥0, m≥0 P {X n,p = m} T n n p z n n! u p v m , (10)
F(z, u, v) = ∑ n≥0, p≥0, m≥0 P {Y n,p = m} T n n p z n n! u p v m . ( 11
)
If we take the recursive generation of the simple families of increasing trees into consideration, we can translate these recurrences into equations for the corresponding generating functions. This gives for the generating function of the ancestor-tree size the non-linear first order differential equation

∂ ∂z G(z, u, v) = v(1 + u) ϕ G(z, u, v) + (1 -v) ϕ T (z) , G(0, u, v) = 0. ( 12
)
The derivative w. r. t. z in the left side of this equation reflects the marking of the root with label 1; in the right side of this equation the factor v reflects the counting of the root, regardless whether the root is one of the chosen nodes or not (which leads to a factor 1 + u). But in the case p = 0, where we do not select any node, the root must not be counted. Thus we have to add the stated correction term. The parameters "Steiner distance" and "ancestor-tree size" are closely related; differences occur only if all selected nodes are hanging on the same subtree. One gets by translating the recursive generation of the simple families of increasing trees a linear first order differential equation that connects both generating functions:

∂ ∂z F(z, u, v) = ϕ ′ T (z) F(z, u, v) + ∂ ∂z G(z, u, v) -vϕ ′ T (z) G(z, u, v) -(1 -v)ϕ ′ T (z) T (z), (13)
with inital value F(0, u, v) = 0. Essential in our analysis will be the knowledge of the asymptotic behaviour of the coefficients

G p (z, v) := p![u p ]G(z, u, v) resp. F p (z, v) := p![u p ]F(z, u, v) near the dominant singularity z = ρ uniformly in a neighbourhood of v = 1.
These singular expansions will be given in the formulae (23) resp. (46). To get (23) we will "pump out" the main term and the order of the remainder term of G p (z, v) from the differential equation ( 12) by induction, where we have to solve a first-order differential equation in every induction step. This is done in the Subsections 3.1-3.4. Using singularity analysis, we can translate this expansion of G p (z, v) into an asymptotic formula for the moment generating function ∑ m≥0 P{X n,p = m}e ms in a neighbourhood of s = 0 for fixed p and n → ∞. To obtain the stated Gaussian limiting distribution result (Theorem 1), we can apply a central limit theorem (the so called quasi power theorem, which is due to Hwang, see [START_REF] Hwang | On Convergence Rates in the Central Limit Theorems for Combinatorial Structures[END_REF]), that is very powerful in particular when dealing with combinatorial structures; this is done in Subsection 3.5.

Since the generating functions for the quantities ancestor-tree size and Steiner distance are closely related by a first order differential equation, we can translate the asymptotic expansion around the dominant singularity z = ρ of G p (z, v) (given by equation ( 23)) into the asymptotic expansion (46) of F p (z, v), which will be established in Subsection 4.1. From this expansion, we obtain also an asymptotic formula for the moment generating function ∑ m≥0 P{Y n,p = m}e ms and the stated normal convergence result (Theorem 2) follows by applying the quasi power theorem; this is done in Subsection 4.2.

For computing the second order terms c p resp. d p in the asymptotic expansion of the expectation resp. of the variance of X n,p , we will consider in Subsection 3.6 the coefficients of the main term in the expansion of G p (z, v) in more detail. Via generating functions, we can solve the recurrence equation that appears, at least in principle, and obtain a formula for the c p 's, as defined in Theorem 1. This formula is obtained in Subsection 3.7 and given as Theorem 13 (with more effort, one could also obtain a formula for d p , but this is omitted here). Due to the close relation between X n,p and Y n,p , we obtain in Subsection 4.3 as Corollary 14 a formula for cp , as defined in Theorem 2.

The quasi power theorem as proven in [START_REF] Hwang | On Convergence Rates in the Central Limit Theorems for Combinatorial Structures[END_REF], which we will apply to our problem, is stated below for the reader's convenience.

M n (s) := E e X n s = ∑ m≥0 P{X n = m}e ms = e H n (s) 1 + O(κ -1 n ) ,
the O-term being uniform for |s| ≤ σ, s ∈ C, σ > 0, where (i) H n (s) = U(s)φ(n) +V (s), with U(s) and V (s) analytic for |s| ≤ σ and independent of n; U ′′ (0) = 0,

(ii) φ(n) → ∞, (iii) κ n → ∞.
Under these assumptions, the distribution of X n is asymptotically Gaussian with the given convergence rate in the Kolmogorov metric:

sup x∈R P X n -E(X n ) V(X n ) ≤ x -Φ(x) = O 1 κ n + 1 φ(n) .
Moreover, the mean and the variance of X n satisfy

E(X n ) = U ′ (0)φ(n) +V ′ (0) + O(κ -1 n ), V(X n ) = U ′′ (0)φ(n) +V ′′ (0) + O(κ -1 n ).
Throughout this paper, we will use the following abbreviations for the rising factorials x n := x(x + 1) • • • (x + n -1), the falling factorials x n := x(x -1) • • • (xn + 1) and the harmonic numbers H n := ∑ 1≤k≤n 1 k . We will also use the notations D u for the differential operator w. r. t. u and N u for the operator that evaluates at u = 0.

3 The ancestor-tree size

Recurrences for the generating functions G p (z, v)

As already pointed out in Subsection 2.2 the main step in the proof of Theorem 1 is a thorough analysis of the asymptotic behaviour of the functions

G p (z, v) := ∂ p ∂u p G(z, u, v) u=0 = N u D p u G(z, u, v) = p![u p ]G(z, u, v) (14)
near the dominant singularity z = ρ uniformly in a neighbourhood of v = 1.

Here we start our analysis by describing how one can obtain the functions

G p (z, v) recursively. It follows immediately from the definition of G(z, u, v), that G 0 (z, v) = G(z, 0, v) = T (z).
The functions G p (z, v), for p ≥ 1, will be obtained recursively. Differentiating equation ( 12) p times w. r. t. u and evaluating at u = 0 gives for p ≥ 1 that

∂ ∂z N u D p u G(z, u, v) = vN u D p-1 u ϕ G(z, u, v) + vN u D p u ϕ G(z, u, v) .
If we denote by ϕ (L) (t) the L-th derivative of ϕ(t), it also holds for p ≥ 1 that

N u D p u ϕ (L) G(z, u, v) = N u D p-1 u ϕ (L+1) G(z, u, v) D u G(z, u, v) = p-1 ∑ l=0 p -1 l N u D l u ϕ (L+1) G(z, u, v) N u D p-l u G(z, u, v) = ϕ (L+1) T (z) G p (z, v) + p-1 ∑ l=1 p -1 l N u D l u ϕ (L+1) G(z, u, v) G p-l (z, v). ( 15
)
Using (3), we get that the functions G p (z, v) satisfy for p ≥ 1 the differential equation

∂ ∂z G p (z, v) = v ϕ ′ T (z) T ′ (z) ϕ T (z) G p (z, v) + vN u D p-1 u ϕ G(z, u, v) + v p-1 ∑ l=1 p -1 l N u D l u ϕ ′ G(z, u, v) G p-l (z, v), (16)
with initial values G p (0, v) = 0. By solving this first-order linear differential equation, we get for p ≥ 1 equations, which define the G p (z, v) recursively, where the auxiliary functions D u N l u ϕ (L) G(z, u, v) for 1 ≤ l < p appear, as defined by [START_REF] Panholzer | Spanning tree size in random binary search trees[END_REF]:

G p (z, v) = v(T ′ (z)) v × × Z z t=0 N u D p-1 u ϕ G(t, u, v) + p-1 ∑ l=1 p -1 l N u D l u ϕ ′ G(t, u, v) G p-l (t, v) T ′ (t) -v dt. (17)

Analyticity of the functions G p (z, v)

In order to prove the analyticity of the functions G p (z, v) within the analytic domain D of T (z) (which will be done in Lemma 8) it is necessary to show that T ′ (z) = 0 for all z within this domain D. But if there would exist a κ ∈ D such that T ′ (κ) = 0, we would get by [START_REF] Bollobás | Mathematical results on scale-free random graphs[END_REF], that ϕ T (κ) = 0 holds as well. Using the integral representation (4) and expanding the polynomial ϕ(t) around T (κ),

ϕ(t) = a 1 (t -T (κ)) + • • • + a d (t -T (κ)) d ,
one gets immediately that the integral is unbounded:

|κ| = Z T (κ) t=0 dt ϕ(t) = ∞.
Thus T ′ (z) = 0 for z ∈ D and therefore the functions T ′ (z) v resp. T ′ (z) -v are for fixed v also analytic for z ∈ D.

Lemma 8. The functions G p (z, v) and N u D p u ϕ (L) G(z, u, v) are for p ≥ 0, 0 ≤ L ≤ d -1 and fixed v analytic within the domain z ∈ D where T (z) is analytic. Their dominant singularities are the dominant singularities of T (z) and are thus located at z = ρ in the aperiodic case, resp. by z = ρe 2πim/q , 0 ≤ m < q, if ϕ(t) has period q.

Proof. We start by considering

G 0 (z, v) = N u G(z, u, v) = T (z) and N u ϕ (L) G(z, u, v) = ϕ (L) T (z) = d ∑ k=L ϕ k k L T k-L (z),
in which instance we know from Theorem 4 that the lemma is true. Moreover, we get that

N u ϕ (d) G(z, u, v) = ϕ d d!.
Using the recursive description (17) of the functions G p (z, v), we will show the lemma for p ≥ 1 by induction. We assume thus, that the lemma is for p ≥ 1 already shown for all G l (z, v) and N u D l u ϕ (L) G(z, u, v) with 0 ≤ l < p and 0 ≤ L ≤ d -1. Since T ′ (z) = 0 for z ∈ D, it follows immediately that the integrand in the representation of G p (z, v) as given by ( 17) is analytic in the considered domain D. The dominant singularities are the dominant singularities of T ′ (z) and thus of T (z). It follows then that the lemma is also true for G p (z, v).

Once the lemma is proven for G p (z, v), we can use for 0 ≤ L ≤ d -1 the recursive description of N u D p u ϕ (L) (G(z, u, v)) stated as equation ( 15), to show that the lemma is also true for these auxiliary functions. Moreover, one gets for p ≥ 1 that

N u D p u ϕ (d) G(z, u, v) = 0.

Singular behaviour of G 1 (z, v)

The next lemma describes the asymptotic behaviour of G 1 (z, v) near z = ρ.

Lemma 9. G 1 (z, v) has for fixed v, |1 -v| ≤ σ and σ small enough in a neighbourhood of the dominant singularity z = ρ the expansion

G 1 (z, v) = α 1 (v)g 1 ∆(z), v 1 - z ρ -(1+δ)v + g 2 ∆(z), v 1 - z ρ -δ
, with g 1 (0, v) = 1, and where g 1 (t, v) and g 2 (t, v) are for fixed v with |1 -v| ≤ σ, σ small enough, analytic around t = 0. Moreover, α 1 (v) is analytic for v with |1 -v| ≤ σ, σ small enough, and given by

α 1 (v) = v δ ρη v C(v), with C(v) = Z ρ t=0 T ′ (t) 1-v dt.
Proof. We start with the integral representation

G 1 (z, v) = v T ′ (z) v Z z t=0 T ′ (t) 1-v dt, ( 18
)
which is obtained from (17).

From Theorem 5 we get via

T ′ (z) = -∆ ′ (z) ∆(z) 2 H ∆(z) -∆(z)H ′ ∆(z) , the local expansion T ′ (z) = δ ρη 1 - z ρ -1-δ H ∆(z) , (19)
where H(t) := H(t) -tH ′ (t) = ∑ k≥0 h k (1k)t k . Thus H(t) = ∑ k≥0 hk t k is analytic around t = 0 with h0 = 1. From this expansion, we get in a neighbourhood of z = ρ the expansions

T ′ (z) 1-v = δ ρη 1-v 1 - z ρ -(1+δ)(1-v) Ĥ ∆(z), v , (20)
T ′ (z) v = δ ρη v 1 - z ρ -(1+δ)v Ȟ ∆(z), v , (21)
with functions Ĥ(t, v) = ∑ k≥0 ĥk (v)t k and Ȟ(t, v) = ∑ k≥0 ȟk (v)t k , that are for fixed v with |1 -v| ≤ σ, σ small enough, analytic around t = 0 with ĥ0 (v) = 1 and ȟ0 (v) = 1.

Next, we consider the integral

Z z t=0 T ′ (t) 1-v dt = Z ρ t=0 T ′ (t) 1-v dt - Z ρ t=z T ′ (t) 1-v dt. ( 22
)
We want to show that the first part of equation ( 22),

C(v) := Z ρ t=0 T ′ (t) 1-v dt,
is an analytic function of v in a neighbourhood of v = 1. This is not completely obvious in advance, since T ′ (z) is not analytic at z = ρ. We will consider the coefficients

c n := ∂ n R ρ t=0 (T ′ (t)) 1-v dt ∂v n v=1 = (-1) n Z ρ t=0 log T ′ (t) n dt in the expansion C(v) = ∑ n≥0 c n n! (v -1
) n and show that they will not grow too fast. We choose ε > 0 small enough, such that the expansion of T ′ (z) as given by ( 19) holds for |1z/ρ| ≤ ε and write

Z ρ t=0 log T ′ (t) n dt = Z ρ(1-ε) t=0 log T ′ (t) n dt + Z ρ t=ρ(1-ε) log T ′ (t) n dt. Since T ′ (z) = 0 in the domain D, log T ′ (z) is bounded in the interval [0, ρ(1 -ε)]. We define M 0 := max z∈[0,ρ(1-ε)] log T ′ (z) and get Z ρ(1-ε) t=0 log T ′ (t) n dt ≤ ρ(1 -ε)M n 0 .
From the expansion (19), we get

log T ′ (z) = log δ ρη + log H(∆(z)) -(1 + δ) log(1 -z/ρ). Defining M 1 := max z∈[ρ(1-ε),ρ] log δ ρη + log H(∆(z)) , we obtain for z ∈ [ρ(1 -ε), ρ]: | log T ′ (z)| ≤ M 1 -(1 + δ) log(1 -z/ρ),
and with the substitution x = 1t/ρ:

Z ρ t=ρ(1-ε) log T ′ (t) n dt ≤ ρ Z ε x=0 (M 1 -(1 + δ) log x) n dx. Since Z ε 0 (log x) n dx = ε n ∑ k=0 (-1) k n k (log ε) n-k ,
we get further

Z ρ t=ρ(1-ε) log T ′ (t) n dt ≤ ρ n ∑ j=0 n j M n-j 1 (-1) j (1 + δ) j ε j ∑ k=0 j k (log ε) j-k (-1) k = ρ ε M n 1 n ∑ k=0 1 + δ M 1 k n! (n -k)! n-k ∑ j-k=0 n -k j -k (-1) j-k (1 + δ) log ε M 1 j-k = ρεM n 1 1 - (1 + δ) log ε M 1 n n ∑ k=0 n! (n -k)! 1 + δ M -(1 + δ) log ε k . Since 1+δ M 1 -(1+δ) log ε < 1, for ε small enough, we obtain the bound Z ρ t=ρ(1-ε) log T ′ (t) n dt ≤ ρ ε (n + 1)! (M 1 -(1 + δ) log ε) n .
Thus we found that c n ≤ ρ ε (n + 1)! (M 1 -(1 + δ) log ε) n + ρεM n 0 , and this gives by majorisation, that C(v) converges for |v| < 1 M 1 -(1+δ) log ε and is analytic therein. For the second part in (22) we obtain

Z ρ t=z T ′ (t) 1-v dt = Z ρ t=z δ ρη 1-v 1 - t ρ -(1+δ)(1-v) Ĥ(∆(t), v)dt = δ ρη 1-v Z ρ t=z ∑ k≥0 ĥk (v)η k 1 - t ρ δk-(1+δ)(1-v) dt = δ ρη 1-v ∑ k≥0 ĥk (v)η k -ρ 1 -t ρ δk-(1+δ)(1-v)+1 ρk -(1 + δ)(1 -v) + 1 ρ t=z = δ ρη 1-v ρ 1 -(1 + δ)(1 -v) 1 - z ρ 1-(1+δ)(1-v) ∑ k≥0 ĥk (v) 1 -(1 + δ)(1 -v) 1 -(1 + δ)(1 -v) + δk η 1 - z ρ k = δ ρη 1-v ρ 1 -(1 + δ)(1 -v) 1 - z ρ 1-(1+δ)(1-v) H(∆(z), v), with H(t, v) := ∑ k≥0 ĥk (v) 1 -(1 + δ)(1 -v) 1 -(1 + δ)(1 -v) + δk t k .
It follows again by majorisation, which is omitted here, that H(t, v) is for fixed v with |1 -v| ≤ σ, σ small enough, in a neighbourhood of t = 0 an analytic function, since Ĥ(t, v) is analytic there.

Combining these results, we get from (18) the expansion

G 1 (z, v) = 1 - z ρ -(1+δ)v v δ ρη v C(v) Ȟ(∆(z), v) + 1 - z ρ -δ - vδ η(1 -(1 + δ)(1 -v)) Ȟ(∆(z), v) H(∆(z), v).
Setting

α(v) := v δ ρη v C(v), g 1 (∆(z), v) := Ȟ(∆(z), v), g 2 (∆(z), v) := - vδ η(1 -(1 + δ)(1 -v)) Ȟ(∆(z), v) H(∆(z), v),
the lemma is proven.

Establishing the singular behaviour of G p (z, v) by induction

The crucial step in proving the normal convergence theorem in our approach is the description of the behaviour of the functions G p (z, v) in a neighbourhood of v = 1 around the dominant singularity z = ρ. This is given in the next lemma.

Lemma 10. The functions G p (z, v) have for for p ≥ 1 and |1 -v| ≤ σ, σ small enough, the following local expansions around the dominant singularity z = ρ:

G p (z, v) = α p (v) 1 - z ρ -pdδv+(p-1)δ + O 1 - z ρ -pdδ+pδ-(3p-2)dδσ , ( 23
)
and for p = 0:

G 0 (z, v) = α 0 (v) 1 - z ρ -δ + O (1) .
The auxiliary functions N u D p u ϕ (L) G(z, u, v) have for p ≥ 1, 0 ≤ L ≤ d -1 and |1 -v| ≤ σ, σ small enough, the following local expansions around the dominant singularity z = ρ:

N u D p u ϕ (L) G(z, u, v) = β p,L (v) 1 - z ρ -pdδv-(d-L-p)δ + O 1 - z ρ -pdδ-(d-1-L-p)δ-(3p-2)dδσ
, and for p = 0:

N u ϕ (L) G(z, u, v) = β 0,L (v) 1 - z ρ -(d-L)δ + O 1 - z ρ -(d-1-L)δ . Moreover we have N u D p u ϕ (d) G(z, u, v) = β p,d (v).
The coefficients α p (v) resp. β p,L (v) are for |1 -v| ≤ σ analytic functions which are given by the following system of recurrences:

α p (v) = vρ (p -1)dδv -(p -1)δ p-1 ∑ l=1 p -1 l β l,1 (v)α p-l (v), for p ≥ 2, β p,L (v) = p-1 ∑ l=0 p -1 l β l,L+1 (v)α p-l (v), for 0 ≤ L ≤ d -1 and p ≥ 1, (24)
where the initial values are given by

β p,d (v) = ϕ d d!, p = 0, 0, p ≥ 1, β 0,L (v) = ϕ d d L η d-L , for 0 ≤ L ≤ d -1, α 0 (v) = 1 η , α 1 (v) = v δ ρη v Z ρ t=0 T ′ (t) 1-v dt. ( 25
)
Proof. First we will treat the special cases. Since

G 0 (z, v) = T (z) resp. N u ϕ (L) G(z, u, v) = ϕ (L) (T (z)), we get from Theorem 5 G 0 (z, v) = 1 ∆(z) H(∆(z)) = 1 η H(∆(z)) 1 - z ρ -δ = 1 η 1 - z ρ -δ + O (1)
,

and for 0 ≤ L ≤ d -1, N u ϕ (L) (G(z, u, v)) = ϕ (L) (T (z)) = d ∑ k=L ϕ k k L T k-L (z) = d ∑ k=L ϕ k k L 1 η k-L H(∆(z)) k-L 1 - z ρ -δ(k-L) = ϕ d d L η d-L 1 - z ρ -δ(d-L) + O 1 - z ρ -δ(d-1-L)
.

Further it follows for L = d that

N u D p u ϕ (d) G(z, u, v) = N u D p u ϕ d d! = ϕ d d!, p = 0, 0, p ≥ 1.
This gives the initial values

α 0 (v) = 1 η , β 0,L (v) = ϕ d d L η d-L for 0 ≤ L ≤ d -1, β p,d (v) = ϕ d d!, p = 0, 0, p ≥ 1.
Of course these functions are constants and therefore analytic. Further it follows from Lemma 9 that the stated expansion holds for G 1 (z, v). We only use the fact that for v with |1 -v| ≤ σ and σ small enough, it holds in a neighbourhood of z = ρ:

1 - z ρ av = O 1 - z ρ a(1-σ) for a > 0, resp. 1 - z ρ av = O 1 - z ρ a(1+σ)
for a < 0.

This gives

G 1 (z, v) = α 1 (v) 1 - z ρ -dδv + O 1 - z ρ -pdδ+pδ-dδσ , with α 1 (v) = v δ ρη v R ρ t=0 (T ′ (t)) 1-v dt. It was proven in Lemma 9 that α 1 (v) is analytic for |1 -v| ≤ σ. Since N u D u ϕ (L) G(z, u, v) = ϕ (L+1) T (z) G 1 (z, v),
we obtain for 0 ≤ L ≤ d -1:

N u D u ϕ (L) G(z, u, v) = β 1,L (v) 1 - z ρ -dδv-(d-1-L)δ + O 1 - z ρ -dδ-(d-2-L)δ-dδσ , with β 1,L (v) = β 0,L+1 (v)α 1 (v).
Therefore the functions β 1,L (v) are also analytic for |1 -v| ≤ σ, and the lemma holds for p = 1.

In the following we will use the expansions

T ′ (z) -v = δ ρη -v 1 - z ρ dδv + O 1 - z ρ (d+1)δ-dδσ and T ′ (z) v = δ ρη v 1 - z ρ -dδv + O 1 - z ρ -(d-1)δ+dδσ
, which follow from (21).

We will now use induction to show the lemma for general p, where we assume that the lemma is already proven for 0 ≤ l < p with p ≥ 2. To do this, we have to examine first the integrand

I(t, v) := N u D p-1 u ϕ G(t, u, v) + p-1 ∑ l=1 p -1 l N u D l u ϕ ′ (G(t, u, v)) G p-l (t, v) T ′ (t) -v
near the dominant singularity t = ρ in the integral representation given by equation (17). By using the induction hypothesis, we obtain then for |1 -v| ≤ σ in a neighbourhood of t = ρ the expansion

I(t, v) = δ ρη -v p-1 ∑ l=1 p -1 l β l,1 (v)α p-l (v) 1 - t ρ -(p-1)dδv+(p-d)δ + O 1 - t ρ -pdδ+(p+1)δ-(3p-3)dδσ . (26)
To obtain a suitable bound for the remainder term of the integral, we will use the following fact. Given an analytic function f (z) with its only dominant singularity at z = ρ, which satisfies for α < -1 in the indented disk D(φ 0 , τ)

:= {z : |z -ρ| ≤ τ, |Arg(z -ρ)| ≥ φ 0 } for τ > 0 and 0 < φ 0 < π/2 the bound f (z) = O 1 -z ρ α . Then for z ∈ D(φ 0 , τ) the bound Z γ f (t) dt = O 1 - z ρ α+1 ,
holds, where the contour γ is for z ∈ D(φ 0 , τ) with |z -ρ| = r ≤ τ and Arg(z -ρ) = φ with |φ| ≥ φ 0 defined by γ := γ 1 + γ 2 , γ 1 := [ρ -τ, ρr], and where γ 2 := {t : |t| = r, Arg(t -ρ) ∈ [-π, φ]} for φ ≤ 0, resp.

γ 2 := {t : |t| = r, -Arg(t -ρ) ∈ [-π, -φ]} for φ > 0.
Next we consider the integral R z t=0 I(t, v)dt, where we split the integration path into parts as described below. The quantity τ is chosen small enough such that above expansion (26) for the integrand I(t, v) holds. We obtain

Z z t=0 I(t, v)dt = Z ρ(1-τ) t=0 I(t, v)dt + δ ρη -v p-1 ∑ l=1 p -1 l β l,1 (v)α p-l (v) Z z t=ρ(1-τ) 1 - t ρ -(p-1)dδv+(p-d)δ dt + Z γ O 1 - t ρ -pdδ+(p+1)δ-(3p-3)dδσ dt = δ ρη -v p-1 ∑ l=1 p -1 l ρ β l,1 (v)α p-l (v) (p -1)dδv -(p -d)δ -1 1 - z ρ -(p-1)dδv+(p-d)δ+1 + Ĉ(v) + O 1 - z ρ -pdδ+(p+1)δ-(3p-3)dδσ+1
, where Ĉ(v) subsumes the contributions

Z ρ(1-τ) t=0 I(t, v)dt - δ ρη -v p-1 ∑ l=1 p -1 l ρ β l,1 (v)α p-l (v) (p -1)dδv -(p -d)δ -1 1 - ρ(1 -τ) ρ -(p-1)dδv+(p-d)δ+1
.

Furthermore, Ĉ(v) is uniformly bounded for |1 -v| ≤ σ, σ small enough. This leads thus to the expansion

G p (z, v) = v T ′ (z) v Z z t=0 I(t, v)dt = v δ ρη v 1 - z ρ -dδv + O 1 - z ρ -(d-1)δ-dδσ Z z t=0 I(t, v)dt = α p (v) 1 - z ρ -pdδv+(p-1)δ + O 1 - z ρ -pdδ+pδ-(3p-2)dδσ , with α p (v) = vρ (p -1)dδv -(p -1)δ p-1 ∑ l=1 p -1 l β l,1 (v)α p-l (v), for p ≥ 2.
Since it follows from the induction hypothesis that the appearing functions β l,1 (v), α p-l (v) are analytic for |1 -v| ≤ σ, and there the denominator (p -1)dδv -(p -1)δ does not vanish, we obtain that α p (v) is also analytic.

Once the expansion is proven for G p (z, v), we can use equation ( 15) to obtain the corresponding results for N u D p u ϕ (L) (G(z, u, v)) . We obtain for 0 ≤ L ≤ d -1 and p ≥ 2 (but it turns out that it holds also for p = 1):

N u D p u ϕ (L) (G(z, u, v)) = β p,L (v) 1 - z ρ -pdδv-(d-L-p)δ + O 1 - z ρ -pdδ-(d-1-L-p)δ-(3p-2)dδσ
, where

β p,L (v) = p-1 ∑ l=0 p -1 l β l,L+1 (v)α p-l (v).
Therefore the functions β p,L (v) are also analytic and the lemma is proven.

Applying the quasi power theorem

From this local expansion of the generating functions G p (z, v) around the dominant singularity z = ρ, as given by ( 23), we obtain immediately via singularity analysis (see [START_REF] Ph | Singularity Analysis of Generating Functions[END_REF]) the expansion for the coefficients:

[z n ]G p (z, v) = ∑ m≥0 P {X n,p = m} T n n! n p v m = q α p (v) n pdδv-(p-1)δ-1 Γ(pdδv -(p -1)δ)ρ n + O n pdδ-pδ-1+(3p-2)dδσ . (27)
The remainder term holds uniformly for |1 -v| ≤ σ, σ small enough. As remarked in the description of Theorem 6, one has to add in the periodic case q ≥ 2 the contributions of the q dominant singularities, which leads to the factor q in formula (27).

Using the asymptotic behaviour of the numbers T n as given by equation ( 9), we obtain by choosing σ small enough the expansion

We obtain U ′ p (0) = pdδ and U ′′ p (0) = pdδ, and get by applying the quasi power theorem (Theorem 7) the stated normal convergence result, Theorem 1. The proof that V p (s) is actually an analytic function in a neighbourhood of s = 0, which is necessary to apply the quasi power theorem, will follow in Subsection 4.1, when we examine the leading coefficients α p (v). We will show that α p (1) > 0 for p ≥ 1 (see equation 36), and since α p (v) is analytic around v = 1, this is sufficient for the analyticity of V p (s) around s = 0.

Examining the leading coefficients in the expansion of G p (z, v)

From the quasi power theorem follows also that the constants c p resp. d p , which denote the second order terms in the expansion of the expectation E(X n,p ) resp. the variance V(X n,p ) in Theorem 1, are given by

c p = V ′ p (0) and d p = V ′′ p (0). (30)
Equation ( 29) shows then, that it is (apart from α p (1)) necessary to compute α ′ p (1) to obtain c p , resp. α ′ p (1) and α ′′ p (1) to obtain d p . Since the recurrence (24) for the α p (v) is quite involved, we will describe in the next lemma how to find the leading coefficients α p (v) by means of generating functions.

Lemma 11. The generating functions A(x, v)

:= ∑ p≥0 α p (v) x p
p! of the leading coefficients α p (v), that are given by (24), satisfy the differential equation

x ∂ ∂x A(x, v) = 1 (dv -1)η vη d A d (x, v) -ηA(x, v) -(v -1) , with A(0) = 1 η . ( 31
)
Proof. To prove this lemma, we also define for 0 ≤ L ≤ d the auxiliary functions B L (x, v) := ∑ p≥0 β p,L (v) x p p! of the leading coefficients β p,L (v). We can then translate the recurrences (24) and initial values (25) into the following system of differential equations:

x ∂ 2 ∂x 2 A(x, v) = vρ (dv -1)δ B 1 (x, v) -B 1 (0, v) ∂ ∂x A(x, v), ∂ ∂x B L (x, v) = B L+1 (x, v) ∂ ∂x A(x, v), for 0 ≤ L ≤ d -1, B d (x, v) = ϕ d d!, A(0, v) = 1 η , ∂ ∂x A(x, v) v=1 = α 1 (v), B L (0, v) = ϕ d d L η d-L , for 0 ≤ L ≤ d.
Next we want to show by induction that

B d-k (x, v) = ϕ d d! k! A k (x, v) for 0 ≤ k ≤ d -1. ( 32
)
For k = 0 the statement is satisfied. If we assume that it is already proven for all B d-l (x, v) with 0 ≤ l < k and k > 0, we obtain

∂ ∂x B d-k (x, v) = ϕ d d! (k -1)! A k-1 (x, v) ∂ ∂x A(x, v) = ϕ d d! k! ∂ ∂x A k (x, v) ,
and thus

B d-k (x, v) = ϕ d d! k! A k (x, v) + κ(v).
But plugging in the initial values for x = 0, we obtain

κ(v) = B d-k (0, v) - ϕ d d! k! A k (0, v) = ϕ d d d-k η k - ϕ d d! k!η k = 0,
and (32) is proven.

We thus obtain

x ∂ 2 ∂x 2 A(x, v) = vρ (dv -1)δ ϕ d d! (d -1)! A d-1 (x, v) - ϕ d d η d-1 ∂ ∂x A(x, v) = v dv -1 ϕ d ρ δ ∂ ∂x A d (x, v) - d η d-1 ∂ ∂x A(x, v) = v dv -1 η d-1 ∂ ∂x A d (x, v) -d ∂ ∂x A(x, v) ,
where we used the definition of η. By integration we obtain

x ∂ ∂x A(x, v) -A(x, v) = v dv -1 η d-1 A d (x, v) -dA(x, v) + κ(v). (33)
Setting x = 0 and taking the initial values into consideration, we obtain from this

κ(v) = - 1 η - v dv -1 η d-1 η d - d η = -v + 1 η(dv -1) . ( 34
)
Combining equations ( 33) and (34), we obtain the first-order differential equation stated in the lemma.

It is easy to verify (but also clear from prior considerations) that

A(x, 1) = 1 η(1 -x) δ , (35)
and thus

α p (1) = p![x p ]A(x, 1) = δ p η = p! η p -1 + δ p . (36)
For general d, we cannot expect to get a simple formula for A(x, v). But for the special case d = 2 (which covers e. g., binary increasing trees), we obtain

A(x, v) = 1 η 1 - α 1 (v)ηz(1 -v) 2v -1 1 - α 1 (v)ηzv 2v -1 , and further for p ≥ 1 α p (v) = p! (2v -1)δ vϕ 2 ρ vρϕ 2 (2v -1)δ α 1 (v) p .
For binary increasing trees, we get with ϕ(t) = (1 + t) 2 eventually

α p (v) = p! v 2v -1 2p-1
, which was already computed in [START_REF] Panholzer | Spanning tree size in random binary search trees[END_REF], to obtain the second order terms of E(X n,p ) and V(X n,p ) for binary search trees. Recall that binary search trees and binary increasing trees are isomorphic.

Computing the second order term for E(X n,p )

Although in general we will not be able to obtain a simple formula for A(x, v) as defined in Lemma 11, we can use the differential equation (31) to compute α ′ p (1) (in principle also for α ′′ p (1), but this is not carried out here), and thus c p in Theorem 1. and E 0 (x) := ηA(x, 1) = 1 (1-x) δ . We obtain then from equation (31) the differential equation

Lemma

(d -1)xE ′ 1 (x) = (dE d-1 0 (x) -1)E 1 (x) + E d 0 (x) -1 -dxE ′ 0 (x), or (d -1)xE ′ 1 (x) = d -1 + x 1 -x E 1 (x) + 1 (1 -x) 1+δ -1 - (1 + δ)x (1 -x) 1+δ , (39)
with E 1 (0) = 0 and E ′ 1 (0) = ηα ′ 1 (1). Solving (39) and plugging in the initial values, we obtain as solution

E 1 (x) = x (1 -x) 1+δ (d -1) Z x t=0 1 -(1 + δ)t -(1 -t) 1+δ t 2 dt + ηα ′ 1 (1)x (1 -x) 1+δ . ( 40
)
Extracting coefficients leads for p ≥ 2 to

[x p ] x (1 -x) 1+δ (d -1) Z x t=0 1 -(1 + δ)t -(1 -t) 1+δ t 2 dt = (-1) p-1 d -1 p-1 ∑ l=1 1 + δ l + 1 -1 -δ p -1 -l 1 l , [x p ] ηα ′ 1 (1)x (1 -x) 1+δ = p + δ -1 p -1 ηα ′ 1 (1)
.

One can simplify the sum e. g. by establishing a recurrence, where one uses the Chu-Vandermonde identity, and obtains for p ≥ 2 p-1

∑ l=1 1 + δ l + 1 -1 -δ p -1 -l 1 l = δ(1 + δ) p -1 + δ p -1 (H p-1+δ -H δ -H p-1 + 1) -δ p + δ p .
This leads for p ≥ 2 to the formula

α ′ p (1) = p! η [x p ]E 1 (x) = p!δ(1 + δ) η p -1 + δ p -1 (H p-1+δ -H δ -H p-1 + 1) - p!δ η p + δ p + p! p -1 + δ p -1 α ′ 1 (1). Since C(v) = R ρ t=0 (T ′ (t)) 1-v dt = R ∞ T =0 ϕ(T )
-v dT , and thus

C ′ (v) = - Z ∞ T =0
log(ϕ(T )) (ϕ(T )) v dT,

we also obtain the stated formula for α ′ 1 (1). From (29) we get then immediately that the constants c p in Theorem 1 are given by

c p = V ′ p (0) = α ′ p (1) α p (1) -pdδΨ(p + δ), (41)
where Ψ(x) := (log Γ(x)) ′ denotes the digamma-function. With Lemma 12, Equation (36) and using

Ψ(p + δ) = Ψ(δ) + H p-1+δ -H δ + 1 δ ,
we obtain the following theorem.

F p (z, v) = T ′ (z) Z z t=0 ∂ ∂t G p (t, v) -vϕ ′ T (t) G p (t, v) T ′ (t) -1 dt. ( 44
)
In order to use the asymptotic expansions for G p (z, v) as given by ( 23), we will integrate by parts and use [START_REF] Bollobás | Mathematical results on scale-free random graphs[END_REF]. We then get

F p (z, v) = G p (z, v) + (1 -v) Z z t=0 G p (t, v) ϕ ′ (T (t)) ϕ(T (t)) dt. ( 45
)
Now we can use (23) and obtain finally for p ≥ 2 the asymptotic expansion

Fig. 1 :

 1 Fig. 1: All 9 planar unary-binary increasing trees of size 4.

  Steiner distance of the three marked nodes {4, 9, 11} is 6.

Fig. 2 :

 2 Fig. 2: An increasing tree with the two parameters under consideration

Theorem 7 .

 7 [H. K. Hwang] Let {X n } n≥1 be a sequence of integral random variables. Suppose that the moment generating function satisfies the asymptotic expression

∑ m≥0 PP

 m≥0 {X n,p = m} v m = α p (v)ηΓ(δ) Γ(pdδv -(p -1)δ) n pdδ(v-1) 1 + O n -δ(1-ε) ,resp. for the moment generating function for |s| small enough, ∑ m≥0 {X n,p = m} e ms = e U p (s) log n+V p (s) 1+ O n -δ(1-ε) ,(28)with U p (s) = pdδ(e s -1) and V p (s) = log α p (e s )ηΓ(δ) Γ(pdδe s -(p -1)δ) .

Theorem 13 . 4 . 1

 1341 The second-order terms c p in the asymptotic expansion of the expectations E(X n,p ) as stated by Theorem 1 are for p ≥ 1 given byc p = p log δ ρη dtpdδ Ψ(δ) + H p -1 + 1pd.Singular behaviour of the generating functions F p (z, v)Since the differential equation (13) connects the generating functions F(z, u, v) and G(z, u, v), we obtain also for F p (z, v) := N u D p u F(z, u, v) = p![u p ]F(z, u, v) a differential equation that links F p (z, v) to the G p (z, v)'s, which were analysed in Section 3. For p ≥ 1,∂ ∂z F p (z, v) = ϕ ′ T (z) F p (z, v) + ∂ ∂z G p (z, v)vϕ ′ T (z) G p (z, v)(43)holds. This differential equation has the solution

F

  p (z, v) = α p (v) (p -1)δ(dv -1)pdδvpδ -

  12. The derivatives α ′ p (1) of the α p (v) as defined by (24) are for p ≥ 2 given by

	α ′ p (1) =	p!δ(1 + δ) η	p -1 + δ p -1	(H p-1+δ -H δ -H p-1 +1)-	p!δ η	p + δ p	+ p!	p -1 + δ p -1	α ′ 1 (1), (37)
	with		α ′ 1 (1) =	δ η	+	δ η	log	δ ρη	-	δ ρη	Z ∞ t=0	log(ϕ(t)) ϕ(t)	dt.	(38)
	Proof. We define E 1 (x) := η ∂ ∂x A(x, v)	v=1

Applying the quasi power theorem

From the singular expansion (46) of F p (z, v) we obtain again by using singularity analysis the following asymptotic expansion for the coefficients:

and where α p (v) is the leading coefficient in the expansion of G p (z, v) around z = ρ as defined in Section 3. Since the α p (v) are for |1 -v| ≤ σ, σ small enough, analytic functions (Lemma 10), and the denominator pdδvpδ -1 does not vanish for p ≥ 2, it follows that the γ p (v) are also analytic there. This leads for |s| small enough to the following asymptotic expansion of the moment generating function of Y n,p :

and where γ p (v) is given by (48). By another application of the quasi power theorem, the normal convergence theorem (Theorem 2) follows, since Ũ′ p (0) = Ũ′′ p (0) = pdδ.

Computing the second order term for E(Y n,p )

To obtain the constants cp = Ṽ ′ p (0) in the expansion of the expectation E(Y n,p ) in Theorem 2, we use equations ( 29) and (50) and get

Differentiating (51), we obtain the following corollary.

Corollary 14. The second-order terms cp in the asymptotic expansion of the expectations E(Y n,p ) as stated by Theorem 2 are for p ≥ 2 given by

where the formula for c p is given in Theorem 13.