ON SOME PARAMETERS IN HEAP ORDERED TREES

KATE MORRIS, ALOIS PANHOLZER, AND HELMUT PRODINGER

Abstract. Heap ordered trees are planted plane trees, labelled in such a way that the labels always increase from the root to a leaf. We study two parameters, assuming that p of the n nodes are selected at random: the size of the ancestor tree of these nodes and the smallest subtree generated by these nodes. We compute expectation, variance, and also the Gaussian limit distribution, the latter as an application of Hwang’s quasi power theorem.

1. Introduction

A heap ordered tree with n nodes (“size n”) can be described as a planted plane tree together with a bijection from the nodes to the set {1, …, n} which is monotonically increasing when going from the root to the leaves.

Figure 1. All 15 heap ordered trees with 4 nodes.

Some recent research papers [9, 10] deal with statistics of the height of the nodes in heap ordered trees. Now, the height of a given node is defined as the number of nodes lying on the unique path from the root to this node. In this paper we consider a simple generalization of

Date: November 6, 2002. Part of this work was done during the second author’s visit to the John Knopfmacher Centre for Applicable

Analysis and Number Theory at the University of the Witwatersrand, Johannesburg, South Africa.

the height: for p given nodes in a heap ordered tree T we consider the size of the ancestor tree of these selected nodes. To be more precise, the ancestor tree is the subtree of T which is spanned by the root and the p chosen nodes and hence it is defined as the tree containing all ascendants of the p given nodes.

Spanning tree size and the Wiener index for binary search trees have been computed in [6] and [8]. The Wiener index of a graph is the sum of all distances between pairs of nodes in the graph. A related parameter of interest is the Steiner distance. The Steiner distance of a graph is the expected distance of two random nodes in the graph. So, the Steiner distance is a scaled down version of the Wiener index; in a sense they behave roughly like path length versus (insertion) depth. For expectations, the concepts are equivalent, but not for higher moments and the limiting distribution. We consider a natural generalization: instead of selecting two random nodes and looking at the distance, we consider p randomly chosen nodes and look at the size of the subtree spanned by these nodes. A different generalization of the Steiner distance can, for example, be found in [3].

In this paper we aim to compute the expectation and variance for the size of the ancestor trees and the Steiner distance in heap ordered trees. Also, we will consider the limiting distributions involved. For the parameters we discuss the distributions turn out to be Gaussian and we will use Hwang’s quasi power theorem, see [5], to determine them. For the convenience of the reader we include this important theorem here.

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

M_{n}(s) = 𝔼(e^{Ω_{n}s}) = ∑_{m≥0} ℙ{Ω_{n} = m}e^{ms} = e^{H_{n}(s)}(1 + O(κ_{n}^{−1})) ,

the O-term being uniform for |s| ≤ τ, s ∈ ℂ, τ > 0, where

(i) H_{n} = 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 Ω_{n} is asymptotically Gaussian:

ℙ \{\frac{Ω_{n} − u′(0)ϕ(n)}{\sqrt{u′′(0)ϕ(n)}} < x\} = Φ(x) + O(\frac{1}{κ_{n}} + \frac{1}{\sqrt{ϕ(n)}}) ,

uniformly with respect to x, x ∈ ℝ. Here Φ(x) denotes the distribution function of the standard normal distribution N (0, 1). Moreover, the mean and variance of Ω_{n} satisfy

𝔼(Ω_{n}) = u′(0)ϕ(n) + v′(0) + O(κ_{n}^{−1}), 𝕍(Ω_{n}) = u′′(0)ϕ(n) + v′′(0) + O(κ_{n}^{−1}) . □

(We will use the letters u and v also in a different context in the paper, but there is no chance of confusion.)

For fixed p and n → ∞, the expected value of both, the ancestor tree, and the Steiner distance, are asymptotic to \frac{p}{2} log n, the difference being in the smaller order terms. To apply the quasi power theorem, an inductive process (w. r. t. p) is used. Part of the difficulty is that a certain trivariate generating function is only implicitly given, and sufficient information must be “pumped out” of this implicit equation.

2. Size of the ancestor tree

For a given tree family let X_{n,p} denote the random variable that counts the size of the ancestor tree of p randomly chosen nodes in a tree of size n and T_{n} the number of trees of size n.

Figure 2. A heap ordered tree of size 10 with the two parameters under consideration; nodes 7 and 10 are labelled.

A simple family of increasing trees (which includes heap ordered trees) is defined by labelled rooted trees in which labels along any branch from the root go in increasing order, see [2]. For this type of problem, it is natural to consider exponential generating functions. In this case one gets, by introducing the generating functions

T (z) = ∑_{n≥0} \frac{T_{n}}{n!} z^{n}  and  G(z, u, v) = ∑_{n≥0,p≥0,m≥0} ℙ \{X_{n,p} = m\} T_{n}\binom{n}{p}\frac{z^{n}}{n!} u^{p}v^{m}

the equations

T′(z) = φ(T (z))  and  \frac{∂}{∂z} G(z, u, v) = v(1 + u)φ(G(z, u, v)) + (1 − v)φ(T (z)), (1)

with initial values T (0) = 0 and G(0, u, v) = 0. The first term in (1) takes care of the instance where the root is labelled and the second term accounts for a non–labelled root. Here the degree generating function φ(t) = ∑_{n≥0} φ_{n}t^{n} satisfies φ_{i} ≥ 0 for i ≥ 1 and φ_{0} > 0. This function is responsible for the recursive generation of these trees. However, here, we are only concerned with the case where each degree can occur with weight one, i. e., with heap ordered trees. We plan to treat the general case in a future publication.

Thus, we have φ(t) = \frac{1}{1−t}, and we obtain the differential equation T′(z) = \frac{1}{1−T (z)}, T (0) = 0, which gives the well-known formula

T (z) = 1 − \sqrt{1 − 2z}

for the exponential generating function T (z). By extracting coefficients we obtain the number of heap ordered trees,

T_{n} = ∏_{k=1}^{n−1}(2k − 1) = \frac{(n − 1)!}{2^{n−1}} \binom{2n − 2}{n − 1}.

The differential equation of interest for G(z, u, v) in the case of heap ordered trees is thus

\frac{∂}{∂z} G(z, u, v) = \frac{v(1 + u)}{1 − G(z, u, v)} + \frac{1 − v}{\sqrt{1 − 2z}} , G(0, u, v) = 0, G(z, u, 1) = 1−\sqrt{1 − 2z(1 + u)} .

It turns out that it is advantageous to make the substitution

H(z, u, v) = \frac{1 − G(z, u, v)}{\sqrt{1 − 2z}}.

Then the differential equation becomes

H(z, u, v) − \frac{v(1 + u)}{H(z, u, v)} − 1 + v = (1 − 2z)\frac{∂}{∂z} H(z, u, v), H(0, u, v) = 1.

Using separation of variables we get the implicit solution

\frac{1}{2} log \frac{1}{1 − 2z} = ∫_{x=1}^{H(z,u,v)} \frac{xdx}{x^{2} − (1 − v)x − v(1 + u)} ,

and by integration we obtain

log \frac{1}{1 − 2z} = log (1 − \frac{(H(z, u, v) − 1)(H(z, u, v) + v)}{vu})
− \frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 + \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + 2 − (1 − v)})  (2)

+ \frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2}) .

Now we replace H(z, u, v) with \frac{1−G(z,u,v)}{\sqrt{1−2z}} in (2) and differentiate with respect to v. In the resulting equation we let v = 1 and solve for \frac{∂}{∂v} G(z, u, v)|_{v=1}. We obtain

\begin{aligned}\frac{∂}{∂v} G(z, u, v)|_{v=1} = & \frac{1}{2}\sqrt{1 − 2z} − \frac{1}{2}\sqrt{1 − 2z(1 + u)} \\ & − \frac{1}{4} \frac{u (log(2 + u − 4z(1 + u) + 2\sqrt{(1 − 2z(1 + u))(1 − 2z)(1 + u)})}{\sqrt{(1 + u)(1 − 2z(1 + u))}} \\ & − \frac{1}{4} \frac{2u log(1 + \sqrt{1 + u})}{\sqrt{(1 + u)(1 − 2z(1 + u))}} . \end{aligned} (3)

From (3) we can as well find \frac{∂^{2}}{∂z∂v} G(z, u, v)|_{v=1} which will be used in Section 3 to compute the expectation for the Steiner distance, see (16). We differentiate equation (2) to get

\frac{∂^{2}}{∂z∂v} G(z, u, v)|_{v=1}

= − \frac{1}{2\sqrt{1 − 2z}} − \frac{1 + u}{2\sqrt{1 − 2z(1 + u)}}

+ (4(1 + u) − \frac{2(1 + u)(1 − 2z)(1 + u) + 2(1 − 2z(1 + u))(1 + u)}{\sqrt{(1 − 2z(1 + u))(1 − 2z)(1 + u)}})

× \frac{u}{4(2 + u − 4z(1 + u))\sqrt{(1 − 2z(1 + u))(1 + u)} + 8(1 − 2z(1 + u))(1 + u)\sqrt{1 − 2z}}

− ( log (2 + u − 4z(1 + u) + 2\sqrt{(1 − 2z(1 + u))(1 − 2z)(1 + u)} )

− log(2 + u + 2\sqrt{1 + u}))\frac{u\sqrt{1 + u}}{4(1 − 2z(1 + u))^{3/2}} .

Next we consider the (formal) expansions

G(z, u, v) = ∑_{p≥0} G_{p}(z, v)u^{p} resp. H(z, u, v) = ∑_{p≥0} H_{p}(z, v)u^{p},

where our aim is to describe the limiting behaviour of [z^{n}]G_{p}(z, v) uniformly in a neighbourhood of v = 1 and then apply a central limit theorem (Hwang’s quasi power theorem) to find the Gaussian limiting distribution of X_{n,p} for fixed p ≥ 1.

Obviously we have G_{p}(z, v) = ∑_{n≥0,m≥0} ℙ \{X_{n,p} = m\} T_{n}\binom{n}{p} \frac{z^{n}}{n!} v^{m} and H_{p}(z, v) = −\frac{G_{p}(z,v)}{\sqrt{1−2z}}

for p ≥ 1 and H_{0}(z, v) = \frac{1−G_{0}(z,v)}{\sqrt{1−2z}}. Since ℙ \{X_{n,0} = m\} = δ_{m,n}, we get immediately G_{0}(z, v) = T (z) = 1 − \sqrt{1 − 2z} and H_{0}(z, v) = 1.

The required expansion for p ≥ 1 is stated as the following lemma.

Lemma 1. The coefficients H_{p}(z, v) have for p ≥ 1 around their (only) dominant singularity z = \frac{1}{2} uniformly for |v − 1| ≤ ε and ε > 0 the expansion

H_{p}(z, v) = h_{p}(v)\frac{1}{(1 − 2z)^{\frac{p(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(p−1)(v+1)}{2}}} ) .

The coefficient generating function C(v, x) = ∑_{p≥1} h_{p}(v)x^{p} of the h_{p}(v) is given implicitly by the equation

\frac{C(v, x)(1 + v + C(v, x))}{vx} = − (\frac{1 + \frac{C(v,x)}{1+v}}{−\frac{1+v}{v} \frac{C(v,x)}{x}} )^{\frac{1−v}{1+v}}

and it holds for

h_{p}(1) = [x^{p}]C(1, x) = −\frac{2}{4^{p}p}\binom{2(p − 1)}{p − 1},

where C(1, x) = −1 + \sqrt{1 − x} and C_{v}(1, x) = \frac{C(1,x)}{2} + \frac{x}{4} \frac{1}{1+C(1,x)} log (\frac{1+ \frac{C(1,x)}{2}}{−2 \frac{C(1,x)}{x}} ). Thus the

expansion for the G_{p}(z, v) for p ≥ 1 is given by

G_{p}(z, v) = −h_{p}(v)\frac{1}{(1 − 2z)^{\frac{p(v+1)−1}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(p−1)(v+1)−1}{2}}} ) .  (4)

Proof. To obtain H_{1}(z, v) and thus G_{1}(z, v) we consider (2) and compare coefficients at u^{0}. We get

[u^{0}] log (1 − \frac{(H(z, u, v) − 1)(H(z, u, v) + v)}{vu})

= [u^{0}] log (1 − \frac{(H_{1}(z, v)u + O(u^{2}))(1 + v + O(u))}{vu}) = log (1 − \frac{1 + v}{v} H_{1}(z, v)) ,

[u^{0}]\frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 + \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + 2 − (1 − v)})

= [u^{0}]\frac{1 − v}{1 + v} \frac{1}{\sqrt{1 + \frac{4v}{(1+v)^{2}} u}} log (1 + \frac{2(H_{1}(z, v)u + O(u^{2}))}{(1 + v)\sqrt{1 + \frac{4v}{(1+v)^{2}} u} + 1 + v} )

= [u^{0}]\frac{1 − v}{1 + v} (1 + O(u)) log(1 + O(u)) = 0,

[u^{0}]\frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2})

= [u^{0}]\frac{1 − v}{1 + v} (1 + O(u)) log (1 − \frac{2(H_{1}(z, v)u + O(u^{2}))}{(1 + v)\sqrt{1 + \frac{4v}{(1+v)^{2}} u} − 1 − v} )

= [u^{0}]\frac{1 − v}{1 + v} (1 + O(u)) log(1 − \frac{1 + v}{v} H_{1}(z, v) + O(u)) = \frac{1 − v}{1 + v} log (1 − \frac{1 + v}{v} H_{1}(z, v)) ,

and further

log (\frac{1}{1 − 2z} ) = \frac{2}{1 + v} log (1 − \frac{1 + v}{v} H_{1}(z, v)) ,

which gives

H_{1}(z, v) = \frac{v}{1 + v} (1 − \frac{1}{(1 − 2z)^{\frac{v+1}{2}}} ) and G_{1}(z, v) = \frac{\sqrt{1 − 2z} v}{1 + v} (\frac{1}{(1 − 2z)^{\frac{v+1}{2}}} − 1) .

Therefore the asymptotic expansion given above holds for p = 1 (although the bound for the remainder term is not tight here) with h_{1}(v) = −\frac{v}{1+v} and thus the stated formula for h_{p}(1) is also valid for p = 1.

Now we assume that the lemma for H_{l}(z, v) resp. G_{l}(z, v) is true for all 1 ≤ l ≤ p and we will show that it then also holds for p + 1. To prove the result for H_{p+1}(z, v), we will consider the coefficients of u^{p} in the equation (2).

ON SOME PARAMETERS IN HEAP ORDERED TREES 7

For the first term in (2), we use the expansion

log (1 − \frac{(H(z, u, v) − 1)(H(z, u, v) + v)}{vu}) = log (1 − \frac{1 + v}{v} H_{1}(z, v)) + log (1 − H̃(z, u, v)) ,

with

\begin{aligned}H̃(z, u, v) & = ∑_{l≥1} H̃_{l}(z, v)u^{l} \\ & = \frac{1}{1 − \frac{1+v}{v} H_{1}(z, v)} (\frac{(H(z, u, v) − 1)(H(z, u, v) + v)}{vu} − \frac{1 + v}{v} H_{1}(z, v)) . \end{aligned}

We get then

[u^{p}] log (1 − \frac{(H(z, u, v) − 1)(H(z, u, v) + v)}{vu}) = − ∑_{j=1}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} H̃_{p_{i}}(z, v)

= −\frac{\frac{1+v}{v} H_{p+1}(z, v)}{1 − \frac{1+v}{v} H_{1}(z, v)} − \frac{\frac{1}{v} ∑_{k=1}^{p} H_{k}(z, v)H_{p+1−k}(z, v)}{1 − \frac{1+v}{v} H_{1}(z, v)} − ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} H̃_{p_{i}}(z, v),

where

H̃_{l}(z, v) = \frac{1}{1 − \frac{1+v}{v} H_{1}(z, v)} \frac{1}{v} ((1 + v)H_{l+1}(z, v) + ∑_{k=1}^{l} H_{k}(z, v)H_{l+1−k}(z, v)) .

Under the assumptions of the lemma we now obtain, for 1 ≤ l ≤ p−1, around the dominant singularity z = \frac{1}{2} in a neighbourhood of v = 1, the uniform expansion

H̃_{l}(z, v) = (1 − 2z)^{\frac{v+1}{2}} (\frac{\frac{1+v}{v} h_{l+1}(v)}{(1 − 2z)^{\frac{(l+1)(v+1)}{2}}} + \frac{\frac{1}{v} ∑_{k=1}^{l} h_{k}(v)h_{l+1−k}(v)}{(1 − 2z)^{\frac{(l+1)(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{l(v+1)}{2}}} ))

= h̃_{l}(v)\frac{1}{(1 − 2z)^{\frac{l(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(l−1)(v+1)}{2}}} ) ,

where

h̃_{l}(v) = \frac{1}{v} ((1 + v)h_{l+1}(v) + ∑_{k=1}^{l} h_{k}(v)h_{l+1−k}(v)) .

With the abbreviations

Ĥ(z, u, v) = ∑_{l≥1} Ĥ_{l}(z, v)u^{l} = \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + 2 − (1 − v)},

â_{l}(v) = [u^{l}]\frac{1}{\sqrt{1 + \frac{4v}{(1+v)^{2}} u}}, b̂_{l}(v) = [u^{l}]\frac{2}{\sqrt{4vu + (1 + v)^{2}} + 2 − (1 − v)},

we get for the coefficients of the second term in (2) the expansion

[u^{p}]\frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 + \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + 2 − (1 − v)})

8 K. MORRIS, A. PANHOLZER, AND H. PRODINGER

= \frac{1 − v}{1 + v} ∑_{k=1}^{p} â_{p−k}(v) ∑_{j=1}^{k} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} Ĥ_{k_{i}}(z, v)

= \frac{1 − v}{1 + v} ∑_{j=1}^{p} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} Ĥ_{p_{i}}(z, v)

+ \frac{1 − v}{1 + v} ∑_{k=1}^{p−1} â_{p−k}(v) ∑_{j=1}^{k} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} Ĥ_{k_{i}}(z, v),

where

Ĥ_{l}(z, v) = ∑_{k=1}^{l} H_{k}(z, v)b̂_{l−k}(v).

Under the assumptions of the lemma we obtain, for 1 ≤ l ≤ p, the uniform expansion

Ĥ_{l}(z, v) = ∑_{k=1}^{l} (\frac{h_{k}(v)}{(1 − 2z)^{\frac{k(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(k−1)(v+1)}{2}}} )) b̂_{l−k}(v)

= ĥ_{l}(v)\frac{1}{(1 − 2z)^{\frac{l(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(l−1)(v+1)}{2}}} ) ,

where

ĥ_{l}(v) = \frac{1}{1 + v} h_{l}(v).

Finally for the third term in (2) we use the expansion

\frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2})

= \frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \frac{1 + v}{v} H_{1}(z, v)) + \frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \overline{H}(z, u, v)) ,

with

\overline{H}(z, u, v) = ∑_{l≥1} \overline{H}_{l}(z, v)u^{l}

= \frac{1}{1 − \frac{1+v}{v} H_{1}(z, v)} (\frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2} − \frac{1 + v}{v} H_{1}(z, v)) .

Further we use the abbreviations

\overline{a}_{l}(v) = [u^{l}]\frac{1}{\sqrt{1 + \frac{4v}{(1+v)^{2}} u}}, \overline{b}_{l}(v) = [u^{l}]\frac{2u}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2}.

We get the expansion

[u^{p}]\frac{1 − v}{\sqrt{4vu + (1 + v)^{2}}} log (1 − \frac{2(H(z, u, v) − 1)}{\sqrt{4vu + (1 + v)^{2}} + (1 − v) − 2})

ON SOME PARAMETERS IN HEAP ORDERED TREES 9

= \frac{1 − v}{1 + v} \overline{a}_{p}(v) log (1 − \frac{1 + v}{v} H_{1}(z, v)) − \frac{1 − v}{1 + v} ∑_{k=1}^{p} \overline{a}_{p−k}(v) ∑_{j=1}^{k} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{H}_{k_{i}}(z, v)

= \frac{1 − v}{1 + v} \overline{a}_{p}(v) log (1 − \frac{1 + v}{v} H_{1}(z, v)) − \frac{1 − v}{1 + v} \frac{\frac{1+v}{v} H_{p+1}(z, v)}{1 − \frac{1+v}{v} H_{1}(z, v)} − \frac{1 − v}{1 + v} \frac{∑_{k=0}^{p−1} H_{k+1}(z, v)\overline{b}_{p−k}(v)}{1 − \frac{1+v}{v} H_{1}(z, v)}

− \frac{1 − v}{1 + v} ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{H}_{p_{i}}(z, v) − \frac{1 − v}{1 + v} ∑_{k=1}^{p−1} \overline{a}_{p−k}(v) ∑_{j=1}^{k} \frac{1}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{H}_{k_{i}}(z, v),

where

\overline{H}_{l}(z, v) = \frac{1}{1 − \frac{1+v}{v} H_{1}(z, v)} ∑_{k=0}^{l} H_{k+1}(z, v)\overline{b}_{l−k}(v).

Now, under the assumptions of the lemma, we obtain, for 1 ≤ l ≤ p − 1, the uniform expansion

\overline{H}_{l}(z, v) = (1 − 2z)^{\frac{v+1}{2}} ∑_{k=0}^{l} (\frac{h_{k+1}(v)}{(1 − 2z)^{\frac{(k+1)(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{k(v+1)}{2}}} )) \overline{b}_{l−k}(v)

= \overline{h}_{l}(v)\frac{1}{(1 − 2z)^{\frac{l(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(l−1)(v+1)}{2}}} ) ,

where

\overline{h}_{l}(v) = \frac{1 + v}{v} h_{l+1}(v).

Comparing coefficients leads to the following equation for H_{p+1}(z, v):

\frac{2}{v} \frac{1}{1 − \frac{1+v}{v} H_{1}(z, v)}H_{p+1}(z, v) =

− \frac{\frac{1}{v} ∑_{k=1}^{p} H_{k}(z, v)H_{p+1−k}(z, v)}{1 − \frac{1+v}{v} H_{1}(z, v)} − ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} H̃_{p_{i}}(z, v)

− \frac{1 − v}{1 + v} ∑_{j=1}^{p} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} Ĥ_{p_{i}}(z, v)

− \frac{1 − v}{1 + v} ∑_{k=1}^{p−1} â_{p−k}(v) ∑_{j=1}^{k} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} Ĥ_{k_{i}}(z, v)

+ \frac{1 − v}{1 + v} \overline{a}_{p}(v) log (1 − \frac{1 + v}{v} H_{1}(z, v)) − \frac{1 − v}{1 + v} \frac{∑_{k=0}^{p−1} H_{k+1}(z, v)\overline{b}_{p−k}(v)}{1 − \frac{1+v}{v} H_{1}(z, v)}

− \frac{1 − v}{1 + v} ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{H}_{p_{i}}(z, v)

− \frac{1 − v}{1 + v} ∑_{k=1}^{p−1} \overline{a}_{p−k}(v) ∑_{j=1}^{k} \frac{1}{j} ∑_{\begin{matrix}k_{1}+···+k_{j}=k \\ k_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{H}_{k_{i}}(z, v).

The asymptotic expansion

H_{p+1}(z, v) = h_{p+1}(v)\frac{1}{(1 − 2z)^{\frac{(p+1)(v+1)}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{p(v+1)}{2}}} ) ,  (5)

follows by inspection, where

\begin{matrix}h_{p+1}(v) = \frac{v}{2}[ − \frac{1}{v} ∑_{k=1}^{p} h_{k}(v)h_{p+1−k}(v) − ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} h̃_{p_{i}}(v) \\ − \frac{1 − v}{1 + v} ∑_{j=1}^{p} \frac{(−1)^{j+1}}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} ĥ_{p_{i}}(v) − \frac{1 − v}{1 + v} ∑_{j=2}^{p} \frac{1}{j} ∑_{\begin{matrix}p_{1}+···+p_{j}=p \\ p_{i}≥1 \end{matrix}} ∏_{i=1}^{j} \overline{h}_{p_{i}}(v)], \end{matrix} (6)

and this part of the lemma is proven. The expansion of G_{p}(z, v) given in (4) follows immediately. It should be remarked, that this detailed description of H_{p+1}(z, v) shown inductively shows as well that the assumptions necessary for the application of singularity analysis are satisfied. The logarithmic remainder term appears for p = 2 due to log (1 − \frac{1+v}{v} H_{1}(z, v)) = −\frac{v+1}{2} log(1 − 2z) and thus also for p ≥ 2.

To get an equation for the coefficient generating function C(v, x) = ∑_{p≥1} h_{p}(v)x^{p} one could of course use equation (6), but it follows much easier directly from (2), when considering which terms give contributions to the main term of H_{p}(z, v). Then one gets

log (1 − \frac{\frac{C(v,x)}{x}(1 + v + C(v, x)) − (v + 1)h_{1}(v)}{v})

− \frac{1 − v}{1 + v} log (1 + \frac{C(v, x)}{1 + v}) + \frac{1 − v}{1 + v} log (1 − \frac{1 + v}{v} (\frac{C(v, x)}{x} − h_{1}(v))) = 0,

or

\frac{C(v, x)(1 + v + C(v, x))}{vx} = − (\frac{1 + \frac{C(v,x)}{1+v}}{−\frac{1+v}{v} \frac{C(v,x)}{x}} )^{\frac{1−v}{1+v}} .  (7)

We easily obtain from (7) the equation \frac{C(1,x)(2+C(1,x))}{x} = −1, which gives

C(1, x) = −1 + \sqrt{1 − x} and
h_{p}(1) = [x^{p}]C(1, x) = −\frac{2}{4^{p}p}\binom{2(p − 1)}{p − 1}, for p ≥ 1.  (8)

This completes the proof of the lemma. □

Using singularity analysis, we get immediately from the above lemma the following expansion, which is uniform for |v − 1| ≤ ε and ε > 0,

∑_{m≥0} ℙ \{X_{n,p} = m\} v^{m} = \frac{n!}{\binom{n}{p}T_{n}} [z^{n}]G_{p}(z, v)

ON SOME PARAMETERS IN HEAP ORDERED TREES 11

= −\frac{p!h_{p}(v)2\sqrt{π}}{Γ (\frac{p(v+1)−1}{2})}n^{\frac{p(v−1)}{2}} (1 + O(\frac{1}{n^{1−ε}} ))

= exp [\frac{p(v − 1)}{2} log n + log (\frac{−2\sqrt{π}p!h_{p}(v)}{Γ(\frac{p(v+1)−1}{2})})] (1 + O(\frac{1}{n^{1−ε}} )),

where we used the asymptotic expansion for the number T_{n} of heap ordered trees

T_{n} = \frac{n!2^{n−1}n^{− \frac{3}{2}}}{\sqrt{π}} (1 + O(\frac{1}{n})).

With the notations of the quasi power theorem, we get

u(s) = \frac{p(e^{s} − 1)}{2} and v(s) = log (\frac{−2\sqrt{π}p!h_{p}(e^{s})}{Γ(\frac{p(e^{s}+1)−1}{2})}).

To apply the quasi power theorem, we need v(s) to be analytic around s = 0, which is true, since h_{p}(1) = −\frac{2}{4^{p}p} \binom{2(p−1)}{p−1} ≠ 0.

We have further

u′(s) = \frac{p}{2}e^{s}, u′′(s) = \frac{p}{2}e^{s}, thus u′(0) = \frac{p}{2}, u′′(0) = \frac{p}{2}.

Therefore we get the following theorem: Theorem 1. 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 heap ordered tree of size n is for p ≥ 1 asymptotically Gaussian, where the convergence rate is of order O (\frac{1}{\sqrt{log n}}):

ℙ\{\frac{X_{n,p} − \frac{p}{2} log n}{\sqrt{\frac{p}{2} log n}} < x\} = Φ(x) + O (\frac{1}{\sqrt{log n}}) ,

and the expectation E_{n,p} = 𝔼(X_{n,p}) and the variance V_{n,p} = 𝕍(X_{n,p}) satisfy

E_{n,p} = \frac{p}{2} log n + v′(0) + O (\frac{1}{n^{1−ε}} ) ,

V_{n,p} = \frac{p}{2} log n + v′′(0) + O (\frac{1}{n^{1−ε}} ) .

□

Remark. By inspection we can get the following expansions

\begin{aligned}[u^{p}]\frac{∂}{∂v} G(z, u, v)|_{v=1} & = ∑_{i=1}^{p}(−1)^{p+i}(p − 1)\underline{i−1} \frac{(2i − 2)!}{(i − 1)! 4^{i}} \frac{1}{(1 − 2z)^{i−1/2}} log \frac{1}{1 − 2z} \\ & + ∑_{i=0}^{p−1} b_{i}(p)\frac{1}{(1 − 2z)^{p−i−1/2}} . \end{aligned}

The computation of the b_{i}(p)’s is cumbersome as they become increasingly involved. However, we were able to obtain b_{1}(p) and b_{2}(p) explicitly:

\begin{aligned}b_{1}(p) & = 2^{−2p−1}\binom{2p}{p} (H_{2p} − H_{p}) , \\ b_{2}(p) & = −H_{2p−1}(2^{2p−3} + \frac{1}{2}\binom{2p − 2}{p} + \binom{2p − 2}{p − 1}) + ∑_{k=0}^{p}(p + 1 − k)\binom{2p − 2}{k}H_{2p−1−k} . \end{aligned}

□

The constant v′(0) in the expectation can also be computed. One gets

v′(s) = \frac{h′_{p}(e^{s})e^{s}}{h_{p}(e^{s})} − \frac{p}{2}e^{s}Ψ (\frac{p(e^{s} + 1) − 1}{2}) , thus v′(0) = \frac{h′_{p}(1)}{h_{p}(1)} − \frac{p}{2}Ψ (\frac{2p − 1}{2}) .

Here Ψ(x) denotes the digamma function Ψ(x) = (log Γ(x))′. For properties of this function we refer the reader to [1]. There remains the calculation of h′_{p}(1) = [x^{p}]C_{v}(1, x). One gets the equation

\begin{aligned}C_{v}(1, x) & = \frac{C(1, x)}{2} + \frac{x}{4(1 + C(1, x))} log (\frac{1 + \frac{C(1,x)}{2}}{−2\frac{C(1,x)}{x}} ) \\ & = \frac{\sqrt{1 − x} − 1}{2} + \frac{x}{4\sqrt{1 − x}} log (\frac{1 + \frac{\sqrt{1−x}−1}{2}}{−2\frac{\sqrt{1−x}−1}{x}} ) . \end{aligned}  (9)

To extract coefficients, we consider

[x^{p}] log (\frac{1 + \frac{\sqrt{1−x}−1}{2}}{−2\frac{\sqrt{1−x}−1}{x}} ) = \frac{1}{p}[x^{p−1}] [log (\frac{1 + \frac{\sqrt{1−x}−1}{2}}{−2\frac{\sqrt{1−x}−1}{x}} )]′

= \frac{1}{p}[x^{p−1}] (−\frac{1}{x\sqrt{1 − x}} + \frac{1}{x}) = −\frac{1}{4^{p}p}\binom{2p}{p},

and one finds with Lemma 2 (below)

\begin{aligned}h′_{p}(1) & = −\frac{1}{4^{p}p}\binom{2(p − 1)}{p − 1} − \frac{1}{4^{p}} ∑_{j=1}^{p−1} \frac{1}{j}\binom{2j}{j}\binom{2(p − 1 − j)}{p − 1 − j} \\ & = −\frac{1}{4^{p}p}\binom{2(p − 1)}{p − 1} − \frac{2}{4^{p}} \binom{2(p − 1)}{p − 1}(H_{2p−2} − H_{p−1}) \\ & = −\frac{1}{4^{p}} \binom{2(p − 1)}{p − 1}(\frac{1}{p} + 2(H_{2p−2} − H_{p−1})). \end{aligned}  (10)

However, the way (9) is expressed is ungainly and the substitution x = \frac{4t}{(1+t)^{2}} is useful for the following computations

C_{v}(1, x) = \frac{2t}{1 − t^{2}} log (\frac{1}{1 + t}) − \frac{t}{1 + t} ,
C_{vv}(1, x) = −\frac{2t(t^{2} + 1)}{(1 − t)^{3}(1 + t)} log^{2} (\frac{1}{1 + t}) + \frac{2t}{(1 − t)^{2}} log (\frac{1}{1 + t}) + \frac{t}{1 − t^{2}} .

Lemma 2.

\begin{matrix}(i) ∑_{j≥1} \frac{1}{j}\binom{2j}{j}z^{j} = 2 log (\frac{1 − \sqrt{1 − 4z}}{2z} ) , \\ (ii) ∑_{j=1}^{p−1} \frac{1}{j}\binom{2j}{j}\binom{2(p − 1 − j)}{p − 1 − j} = \binom{2(p − 1)}{p − 1}(H_{2p−2} − H_{p−1}) . \end{matrix}

Proof. (i) It is easier to prove the equivalent result

\begin{aligned}∑_{j≥1} \binom{2j}{j}z^{j−1} & = 2\frac{d}{dz} [log (\frac{1 − \sqrt{1 − 4z}}{2z} )] \\ & = \frac{4}{\sqrt{1 − 4z}(1 − \sqrt{1 − 4z})} − \frac{2}{z} = \frac{1}{z} [\frac{1}{\sqrt{1 − 4z}} − 1] . \end{aligned}

Now, it is well known that

∑_{j≥0} \binom{2j}{j}z^{j} = \frac{1}{\sqrt{1 − 4z}} ,

and thus

∑_{j≥1} \binom{2j}{j}z^{j−1} = \frac{1}{z} [\frac{1}{\sqrt{1 − 4z}} − 1] ,

which proves the first part of the lemma. (ii) We use the substitution

z = \frac{u}{(1 + u)^{2}} , dz = \frac{1 − u}{(1 + u)^{3}} du, \sqrt{1 − 4z} = \frac{1 − u}{1 + u},

to simplify the given summation as follows

∑_{j=1}^{p−1} \frac{1}{j}\binom{2j}{j}\binom{2(p − 1 − j)}{p − 1 − j} = [z^{p−1}]\frac{1}{\sqrt{1 − 4z}} log (\frac{1 − \sqrt{1 − 4z}}{2z} )^{2}

= \frac{1}{2πi} ∮ \frac{(1 + u)^{2p−2}}{u^{p}} 2 log(1 + u)du

= [u^{p−1}]2(1 + u)^{2p−2} log(1 + u)

= (−1)^{p}[u^{p−1}]2(1 − u)^{2p−2} log (\frac{1}{1 − u})

= 2(−1)^{p}\binom{−p}{p − 1}(H_{−p} − H_{−2p+1})

= 2\binom{2p − 2}{p − 1}(H_{2p−2} − H_{p−1}) .

□

We can determine the constant term v′(0) in the asymptotic expansion of the expectation E_{n,p} given above:

v′(0) = \frac{1}{2} + p(H_{2p−2} − H_{p−1}) − \frac{p}{2}Ψ(\frac{2p − 1}{2})

= \frac{1}{2} + p(H_{2p−2} − H_{p−1}) − \frac{p}{2} (2H_{2p−2} − H_{p−1} + Ψ(\frac{1}{2})) = −\frac{p}{2}H_{p} + \frac{p}{2}γ + p log 2.

Next we compute v′′(0) in the variance. We obtain

v′′(s) = \frac{h′′_{p}(e^{s})e^{2s}}{h_{p}(e^{s})} + \frac{h′_{p}(e^{s})e^{s}}{h_{p}(e^{s})} − \frac{(h′_{p}(e^{s}))^{2}e^{2s}}{h_{p}^{2}(e^{s})}

− \frac{p}{2}e^{s}Ψ(\frac{p(e^{s} + 1) − 1}{2}) − \frac{p^{2}}{4} e^{2s}Ψ′(\frac{p(e^{s} + 1) − 1}{2}) ,

v′′(0) = \frac{h′′_{p}(1)}{h_{p}(1)} + \frac{h′_{p}(1)}{h_{p}(1)} − \frac{(h′_{p}(1))^{2}}{h_{p}^{2}(1)} − \frac{p}{2}Ψ(\frac{2p − 1}{2}) − \frac{p^{2}}{4} Ψ′(\frac{2p − 1}{2}) .

Firstly, we are required to calculate h′′_{p}(1) = [x^{p}]C_{vv}(1, x), namely

[x^{p}]( − \frac{2t(t^{2} + 1)}{(1 − t)^{3}(1 + t)} log^{2} (\frac{1}{1 + t}) + \frac{2t}{(1 − t)^{2}} log (\frac{1}{1 + t}) + \frac{t}{1 − t^{2}} ) .  (11)

We confine ourselves to considering the first few terms only. From the series expansion of (12) we can produce the local expansion around the dominant singularity x = 1 and use singularity analysis [4]:

h′′_{p}(1) = [x^{p}]( − \frac{log^{2} 2}{4}(1 − x)^{−3/2} + (\frac{1}{2} − \frac{log 2}{4}) (1 − x)^{−1/2} + O(1))

= −\frac{log^{2} 2}{4}\binom{−3/2}{p} + (\frac{1}{2} − \frac{log 2}{4}) \binom{−1/2}{p} + O(1).

(12)

From this it follows that

v′′(0) = −\frac{1}{2} p log p + p( log 2 − \frac{5}{4}) + \frac{1}{8} log 2 + \frac{15}{16} − \frac{1}{4} log^{2} 2 + O(p^{−1}) .  (13)

3. The Steiner Distance

An analogous approach works for the Steiner distance. Here Y_{n,p} will denote the random variable that counts the Steiner distance of p randomly chosen nodes in a tree of size n of a given tree family.

For increasing trees we get, by introducing the generating function

F (z, u, v) = ∑_{n≥0,p≥0,m≥0} ℙ \{Y_{n,p} = m\} T_{n} \binom{n}{p}\frac{z^{n}}{n!} u^{p}v^{m}

the equation

\frac{∂}{∂z} F (z, u, v) = φ′(T (z))F (z, u, v) + \frac{∂}{∂z} G(z, u, v) − vφ′(T (z))G(z, u, v) − (1 − v)φ′(T (z))T (z), (14)

Figure 3. The probability distributions of the ancestor tree for n = 30, p = 1, …, 20.

with initial value F (0, u, v) = 0. The generating functions T (z) and G(z, u, v) are as defined in Section 2. The first two terms in (14) arise when the root is labelled and the last two terms represent the corrections arising when the root is not labelled.

In this paper we only look at φ(t) = \frac{1}{1−t} which is the special case of heap ordered trees. Therefore the Steiner distance requires the study of the differential equation

\frac{∂}{∂z} F (z, u, v) = \frac{∂}{∂z} G(z, u, v) + F (z, u, v)\frac{1}{1 − 2z} − G(z, u, v)\frac{v}{1 − 2z} − \frac{1 − v}{1 − 2z} (1 − \sqrt{1 − 2z}).

This is a first order differential equation. We solve for F (z, u, v) and get

F (z, u, v) = \frac{1}{\sqrt{1 − 2z}} ∫_{0}^{z} \sqrt{1 − 2t} [\frac{∂}{∂t}G(t, u, v) − G(t, u, v)\frac{v}{1 − 2t} − \frac{1 − v}{1 − \sqrt{1 − 2t}}] dt . (15)

For the expectation we differentiate F (z, u, v) with respect to v and let v = 1 to obtain

\begin{matrix}\frac{∂}{∂v} F (z, u, v)|_{v=1} = \frac{1}{\sqrt{1 − 2z}} ∫_{0}^{z} \sqrt{1 − 2t}[\frac{∂^{2}}{∂v∂t}G(t, u, v)|_{v=1} − \frac{∂}{∂v} G(t, u, v)|_{v=1} \frac{1}{1 − 2t} \\ −\frac{1 − \sqrt{1 − 2t(1 + u)}}{1 − 2t} + \frac{1}{1 − \sqrt{1 − 2t}}]dt , \end{matrix} (16)

since G(z, u, v)|_{v=1} = 1 − \sqrt{1 − 2z(1 + u)}. This integration is cumbersome, so instead of performing it we find the coefficients u^{p} in (16) and then we consider the dominant term

\begin{matrix}[u^{p}]\frac{∂}{∂v} F (z, u, v)|_{v=1} = [u^{p}]\frac{1}{\sqrt{1 − 2z}} ∫_{0}^{z} \sqrt{1 − 2t}[\frac{∂^{2}}{∂v∂t}G_{p}(t, v)|_{v=1} − \frac{∂}{∂v} G_{p}(t, v)|_{v=1} \frac{1}{1 − 2t} \\ − \frac{1 − \sqrt{1 − 2t(1 + u)}}{1 − 2t} + \frac{1}{1 − \sqrt{1 − 2t}}]dt \\ = (\frac{ph_{p}(1) log(1 − 2z)}{(1 − 2z)^{p−1/2}} − \frac{h′_{p}(1)}{(1 − 2z)^{p−1/2}} + \frac{h′_{p}(1)}{(1 − 2z)^{1/2}} ) + O(\frac{log(1 − 2z)}{(1 − 2z)^{p−3/2}} ) \\ − [u^{p}]\frac{1}{\sqrt{1 − 2z}} ∫_{0}^{z} \frac{1 − \sqrt{1 − 2t(1 + u)}}{\sqrt{1 − 2t}}dt , \end{matrix} ; (17)

where h_{p}(1) and h′_{p}(1) were computed in (8) and (10) respectively. It is not difficult to see that

[u^{p}]\frac{1}{\sqrt{1 − 2z}} ∫_{0}^{z} \frac{1 − \sqrt{1 − 2t(1 + u)}}{\sqrt{1 − 2t}}dt = O (\frac{1}{(1 − 2z)^{p−1/2}} ) ,

therefore the main contribution comes from ph_{p}(1) log(1 − 2z)/(1 − 2z)^{p−1/2}.

We find the expected value of the Steiner distance, 𝔼(Y_{n,p}), by dividing (17) by our normalizing constant \binom{n}{p}^{−1} \frac{n!}{1·3···(2n−3)} and then reading off the coefficient of z^{n} in the resulting equation. Firstly, looking at the dominant term in (17) we see that

E_{n,p} = [z^{n}]\frac{\binom{n}{p}1 · 3 ⋯ (2n − 3)}{n!} \frac{ph_{p}(1) log(1 − 2z)}{(1 − 2t)^{p−1/2}}

= [z^{n}]\frac{\binom{n}{p}1 · 3 ⋯ (2n − 3)}{n!} \frac{−p\frac{2}{p4^{p}} \binom{2(p−1)}{p−1} log(1 − 2z)}{(1 − 2z)^{p−1/2}} ∼ \frac{p}{2} log n ,

(18)

since we have the following

[z^{n}]\frac{1}{(1 − 2z)^{p−1/2}} log(1 − 2z) = −2^{n}[z^{n}]\frac{1}{(1 − z)^{p−1/2}} log \frac{1}{1 − z}

= −2^{n}\binom{n + p − 3/2}{n}(H_{n+p−3/2} − H_{p−3/2})

∼ −2^{n} \frac{n^{p−3/2}}{Γ(p − \frac{1}{2})} log n (n → ∞, p fixed) ,

as well as \frac{n!}{1·3···(2n−3)} ∼ 2^{1−n}n^{3/2}\sqrt{π} and \binom{n}{p} ∼ \frac{n^{p}}{p!} .

To obtain limiting theorems for the distribution of Y_{n,p}, we want to apply the quasi power theorem again and will therefore require for |v − 1| ≤ ε a uniform expansion of F_{p}(z, v) = [u^{p}]F (z, u, v) around the dominant singularity z = \frac{1}{2}. From equation (15) we obtain immediately

F_{p}(z, v) = \frac{1}{\sqrt{1 − 2z}} ∫_{t=0}^{z} \sqrt{1 − 2t} (\frac{∂}{∂t}G_{p}(t, v) − \frac{v}{1 − 2t}G_{p}(t, v)) dt.  (19)

We will now use the following more detailed expansion of G_{p}(z, v) which follows from the proof of Lemma 1:

G_{p}(z, v) = −h_{p}(v)\frac{1}{(1 − 2z)^{\frac{p(v+1)−1}{2}}} + ∑_{\begin{matrix}1≤k≤p−1, \\ 0≤j≤p−k \end{matrix}} α_{p,k,j}(v)\frac{log^{j}(1 − 2z)}{(1 − 2z)^{\frac{k(v+1)−1}{2}}} + α_{p,0,0}(v)\sqrt{1 − 2z}.

This is also used to obtain the bound for the remainder term given below.

The integrand in (19) is then given by

\sqrt{1 − 2t} (\frac{∂}{∂t}G_{p}(t, v) − \frac{v}{1 − 2t}G_{p}(t, v))

= \sqrt{1 − 2t} (\frac{−h_{p}(v)(p(v + 1) − 1)}{(1 − 2t)^{\frac{p(v+1)+1}{2}}} + \frac{vh_{p}(v)}{(1 − 2t)^{\frac{p(v+1)+1}{2}}} + O (\frac{log(1 − 2t)}{(1 − 2t)^{\frac{(p−1)(v+1)+1}{2}}} ))

= −\frac{h_{p}(v)(p − 1)(v + 1)}{(1 − 2t)^{\frac{p(v+1)}{2}}} + O (\frac{log(1 − 2t)}{(1 − 2t)^{\frac{(p−1)(v+1)}{2}}} ) ,

and we get thus for p ≥ 2 the expansion

F_{p}(z, v) = −\frac{h_{p}(v)(p − 1)(v + 1)}{p(v + 1) − 2} \frac{1}{(1 − 2z)^{\frac{p(v+1)−1}{2}}} + O (\frac{log(1 − 2z)}{(1 − 2z)^{\frac{(p−1)(v+1)−1}{2}}} ) .

Using singularity analysis to extract coefficients leads to

[z^{n}]F_{p}(z, v) = −\frac{h_{p}(v)(p − 1)(v + 1)}{p(v + 1) − 2} \frac{2^{n}n^{\frac{p(v+1)−1}{2} −1}}{Γ(\frac{p(v+1)−1}{2})} (1 + O (\frac{1}{n^{1−ε}} )) ,

and furthermore

∑_{m≥0} ℙ(Y_{n,p} = m)v^{m} = \frac{n!}{\binom{n}{p}T_{n}} [z^{n}]F_{p}(z, v)

= −\frac{2\sqrt{π}p!(p − 1)(v + 1)h_{p}(v)}{Γ(\frac{p(v+1)−1}{2})(p(v + 1) − 2)}n^{\frac{p(v−1)}{2}} (1 + O (\frac{1}{n^{1−ε}} )) .

With the notations used in the quasi power theorem we have

u(s) = \frac{p(e^{s} − 1)}{2}, v(s) = log (\frac{−2\sqrt{π}p!(p − 1)(e^{s} − 1)h_{p}(e^{s})}{Γ(\frac{p(e^{s}+1)−1}{2})(p(e^{s} + 1) − 2)}) ,

which gives

u′(0) = \frac{p}{2}, u′′(0) = \frac{p}{2}.

For p ≥ 2, v(1) ≠ 0 since h_{p}(1) < 0 and thus the quasi power theorem is applicable. On the other hand, for p = 1 one knows a priori, from the combinatorial description, that ℙ{Y_{n,1} = 1} = 1 for n ≥ 1.

For the constant v′(0) in the expectation E_{n,p} = 𝔼(Y_{n,p}) we compute

v′(s) = [log(e^{s} + 1) + log (h_{p}(e^{s})) − log (p(e^{s} + 1) − 2) − log Γ(\frac{p(e^{s} + 1) − 1}{2})]′

= \frac{e^{s}}{e^{s} + 1} + \frac{h′_{p}(e^{s})e^{s}}{h_{p}(e^{s})} − \frac{pe^{s}}{p(e^{s} + 1) − 2} − \frac{pe^{s}}{2} Ψ(\frac{p(e^{s} + 1) − 1}{2}),

and further

v′(0) = \frac{h′_{p}(1)}{h_{p}(1)} − \frac{p}{2}Ψ(\frac{2p − 1}{2}) − \frac{1}{2(p − 1)} = −\frac{p}{2}H_{p} + \frac{p}{2}γ + p log 2 − \frac{1}{2(p − 1)}.

We note that this gives us the expected value with a higher accuracy than (18) and it leads to the following theorem.

Theorem 2. The distribution of the random variable Y_{n,p}, which counts the Steiner distance of p randomly chosen nodes in a random heap ordered tree of size n is for p ≥ 2 asymptotically Gaussian, where the convergence rate is of order O(\frac{1}{\sqrt{log n}}):

ℙ\{\frac{Y_{n,p} − \frac{p}{2} log n}{\sqrt{\frac{p}{2} log n}} < x\} = Φ(x) + O (\frac{1}{\sqrt{log n}}) ,

and the expectation E_{n,p} = 𝔼(Y_{n,p}) and the variance V_{n,p} = 𝕍(X_{n,p}) satisfy

E_{n,p} = \frac{p}{2} log n − \frac{p}{2}H_{p} + \frac{p}{2}γ + p log 2 − \frac{1}{2(p − 1)} + O (\frac{1}{n^{1−ε}} ) ,
V_{n,p} = \frac{p}{2} log n + v′′(0) + O (\frac{1}{n^{1−ε}} ) .
□

For the proof, it remains to discuss the variance. Since we have obtained the variance of the size of the ancestor tree in (13), we can easily get the variance of the Steiner distance. It follows that

v′′(s) = \frac{e^{s}}{e^{s} + 1} − \frac{e^{2s}}{e^{s} + 1} + \frac{h′′_{p}(e^{s})e^{s}}{h_{p}(e^{s})} + \frac{h′_{p}(e^{s})e^{s}}{h_{p}(e^{s})} − \frac{(h′_{p}(e^{s}))^{2}e^{2s}}{h_{p}^{2}(e^{s})}

− \frac{pe^{s}}{p(e^{s} + 1) − 2} + \frac{p^{2}e^{2s}}{(p(e^{s} + 1) − 2)^{2}}

− \frac{pe^{s}}{2} Ψ(\frac{p(e^{s} + 1) − 1}{2}) − \frac{p^{2}e^{2s}}{4} Ψ′(\frac{p(e^{s} + 1) − 1}{2}) ,

where h′′_{p}(1) is given by (12) and furthermore,

v′′(0) = \frac{3}{4} + \frac{h′′_{p}(1)}{h_{p}(1)} + \frac{h′_{p}(1)}{h_{p}(1)} − \frac{(h′_{p}(1))^{2}}{h_{p}^{2}(1)} − \frac{p}{2(p − 1)} + \frac{p^{2}}{4(p − 1)^{2}}

− \frac{p}{2}Ψ(\frac{2p − 1}{2}) − \frac{p^{2}}{4} Ψ′(\frac{2p − 1}{2})

= −\frac{p}{2} log p + p (log 2 − \frac{5}{4}) + \frac{1}{8} log 2 + \frac{23}{16} − \frac{1}{4} log^{2} 2 + O(p^{−1}) .

Figure 4. The probability distributions of the Steiner distance for n = 30, p = 2, …, 20.

References

[1] M. Abramowitz and I.A. Stegun. Handbook of Mathematical Functions. Dover, 1972.

[2] F. Bergeron, F. Flajolet and B. Salvy. Varieties of Increasing Trees. Lecture Notes in Computer Science, 581:24–48, 1992.

[3] P. Dankelmann, O. R. Oellermann and H. C. Swart. The Average Steiner Distance of a Graph. Journal of Graph Theory, 22:15–22, 1996.

[4] P. Flajolet and A. Odlyzko. Singularity Analysis of Generating Functions. SIAM Journal of Discrete Mathematics, 3:216–240, 1990.

[5] H.-K. Hwang. On Convergence Rates in the Central Limit Theorems for Combinatorial Structures. European Journal of Combinatorics, 19:329–343, 1998.

[6] H. Mahmoud and R. Neininger. Distribution of Distances in Random Binary Search Trees. The Annals of Applied Probability, accepted for publication, 2002.

[7] A. Panholzer. The distribution of the size of the ancestor tree and of the induced spanning subtree for random trees, submitted, 2002.

[8] A. Panholzer and H. Prodinger. Spanning tree size in random binary search trees, submitted, 2002.

[9] H. Prodinger. Depth and Path Length of Heap Ordered Trees. International Journal of Foundations of Computer Science, 7:293-299, 1996.

[10] H. Prodinger. The Level of Nodes in Heap Ordered Trees. http://www.wits.ac.za/helmut/abstract/ abs 126.htm, 1996.

[11] R. Neininger. Wiener Index of Random Trees. Combinatorics, Probability and Computing, accepted for publication, 2002.

Kate Morris, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

E-mail address: kate@maths.wits.ac.za

Alois Panholzer, Institut für Algebra und Computermathematik, TU Wien, Wiedner Hauptstr. 8-10, 1040 Wien, Austria

E-mail address: Alois.Panholzer@tuwien.ac.at

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

E-mail address: helmut@maths.wits.ac.za