MOMENTS OF LEVEL NUMBERS OF LEAVES IN BINARY TREES

ALOIS PANHOLZER AND HELMUT PRODINGER

Abstract. For the random variable “height of leaf j in a binary tree of size n” we derive closed formulæ for all moments. The more general case of t–ary trees is also considered.

1. Introduction

We reexamine the heights of leaves (enumerated from left to right) in binary trees and, more generally, t–ary trees.

The expectations go back to Kirschenhofer [5], and the variance to Gutjahr [3]. For higher moments, Gutjahr had to resort to analytic techniques. However, we are able to produce an explicit formula for the s–th moment, for general s. The result is “closed form,” as it comprised only a number of summands that depends on s, not on n or j, where n denotes the size of the tree and j the number of the leaf in consideration.

From this explicit result, asymptotic formulæ, as given by Gutjahr, are of course corollaries for which we don’t need more than Stirling’s approximation for the factorials.

In a follow–up paper to [5], Kirschenhofer considered in [7] also t–ary trees (binary trees are the instance t = 2). He treated the expectation with a complicated analytic technique (“diagonalization method”) because he believed that explicit enumeration is not feasible. However, we disproof this claim by giving an exact formula for the s-th (factorial) moment. This time, it is not “closed form,” but we can get asymptotics for the expectations by rather elementary techniques (Stirling’s formula and approximation of a sum by an integral).

2. The height of leaves in binary trees

We denote by B the family of binary trees, sometimes called extended binary trees, which is defined by the formal identity

B =  + B  B  (1)

where ◯ is the symbol for an internal node and □ is the symbol for a leaf or external node.

The family of objects from B with exactly n internal nodes is denoted by B_{n}. Further we write B_{n} for the number of elements from B_{n}. Finally we denote with B(z) = ∑_{n≥0} B_{n}z^{n} the ordinary generating function of the B_{n}’s.

Let us state the following classic results that we will need in the sequel:

B(z) = 1 + zB^{2}(z) = \frac{1 − \sqrt{1 − 4z}}{2z}; B_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Assume that the leaves are labelled with the numbers 0, 1, …, n from left to right and that the distance (depth, height) of a leaf is given by the number of internal nodes on the path from the root to the leaf. This defines random variables X_{n,j} assuming that all binary trees of size n are equally likely.

1This research was supported by the Austrian Research Society (FWF) under the project number P12599-MAT

Date: March 17, 1998.

Kirschenhofer [5, 6] has obtained the following explicit formula for the expectations (see [8] for more results);

𝔼(X_{n,j}) = \frac{2(2j + 1)(2n − 2j + 1)}{n + 2} \begin{matrix}\binom{2j}{j} & \binom{2n−2j}{n−j} \\ ( & {2n \atop n} & ) \end{matrix} − 1 for 0 ≤ j ≤ n .

Gutjahr obtained the variance 𝕍(X_{n,j}) in [3]; unfortunately, this paper was overlooked during the preparation of our paper [8].

Studying the higher moments, Gutjahr writes:

“There is little hope to find a closed expression for the third moment.”

This statement is too pessimistic, since we will find explicit formulæ for all (factorial) moments in the sequel. Since the usual moments can be obtained from them by linear combinations with Stirling numbers as coefficients, we have also explicit formulæ for all usual moments.

Let f_{n,j,l} denote the number of binary trees of size n, where the leaf labelled with j has height l. Then we get for the trivariate generating function F (z, u, v) of the f_{n,j,l}, defined by ∑_{n,j,l} f_{n,j,l}z^{n}u^{j}v^{l} the functional equation

F (z, u, v) = 1 + zvF (z, u, v)B(z) + zuvF (z, u, v)B(zu) .  (2)

This leads immediately to the solution

F (z, u, v) = \frac{1}{1 − zvB(z) − zuvB(zu)} .  (3)

This appears in [8] and in [3]. The s–th factorial moment 𝔼\underline{s}(X_{n,j}) is given by

𝔼\underline{s}(X_{n,j}) = \frac{1}{B_{n}} [z^{n}u^{j}]\frac{∂^{s}}{∂v^{s}} F (z, u, v)|_{v=1}.

Now, a routine calculation (that is easy to verify by induction) shows that

\frac{∂^{s}}{∂v^{s}} F (z, u, v)|_{v=1} = 2s!\frac{(2 − (X + Y))^{s}}{(X + Y)^{s+1}} = 2s! ∑_{l=0}^{s} \binom{s}{l}(−1)^{s−l}2^{l} \frac{1}{(X + Y)^{l+1}} ,

with

X = \sqrt{1 − 4z}  and  Y = \sqrt{1 − 4zu},

so that our task is reduced to find explicit formulæ for

[z^{n}u^{j}]\frac{1}{(X + Y)^{q}} .

First we compute the coefficients of 1/(1 + \sqrt{1 − 4x})^{q}; for that, we use the substitution x = t/(1 + t)^{2} and the Lagrange inversion formula:

[x^{k}]\frac{1}{(1 + \sqrt{1 − 4x})^{q}} = \frac{1}{k} [t^{k−1}](1 + t)^{2k} \frac{d}{dt} \frac{1}{(1 + \sqrt{1 − \frac{4t}{(1+t)^{2}}} )^{q}}

= \frac{1}{k} [t^{k−1}](1 + t)^{2k} \frac{d}{dt} (\frac{1 + t}{2})^{q}

= \frac{q}{2^{q}} \frac{1}{k + q} \binom{2k + q − 1}{k}.

Hence

\frac{1}{(X + Y)^{q}} = \frac{1}{(1 − 4z)^{q/2} (1 + \sqrt{1 − \frac{4z(u−1)}{1−4z}} )^{q}}

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

Thus

[z^{n}u^{j}]\frac{1}{(X + Y)^{q}} = ∑_{j≤k≤n}(−1)^{k−j}\binom{k}{j}\frac{q}{2^{q}} \frac{1}{k + q} \binom{2k + q − 1}{k}4^{n−k}\binom{n − 1 + \frac{q}{2}}{n − k}.

To evaluate the remaining sum we use Zeilberger’s algorithm [2, 9]. (Alternative proofs, e. g. by the use of hypergeometric series, would also be possible.) Let

F (n, k) = (−1)^{k−j}\binom{k}{j}\frac{q}{2^{q}} \frac{1}{k + q} \binom{2k + q − 1}{k}4^{n−k}\binom{n − 1 + \frac{q}{2}}{n − k},

then we find

(n − j + 1)(n + q + 1)F (n + 1, k) − (2n + q)(2n + q − 2j + 1)F (n, j) = G(n, k + 1) − G(n, k)

with

R(n, k) = −\frac{2(2n + q)(k + q)(k − j)}{n + 1 − k}  and  G(n, k) = F (n, k)R(n, k).

Now set

f(n) = ∑_{k∈ℤ}F (n, k),

then we obtain by summing (since the right side telescopes)

(n − j)(n + q)f(n) = (2n + q − 2)(2n + q − 2j − 1)f(n − 1),

with the initial value

f(j) = \frac{q}{2^{q}} \frac{1}{j + q} \binom{2j + q − 1}{j},

which gives by iteration

f(n) = \frac{q}{2^{q}} \frac{1}{j + q} \binom{2j + q − 1}{j} ∏_{k=j+1}^{n} \frac{(2k + q − 2)(2k + q − 2j − 1)}{(k − j)(k + q)}

= \frac{q}{2^{q}} \frac{1}{j + q} \binom{2j + q − 1}{j}\frac{(j + q)!}{(n − j)!(n + q)!} ∏_{k=j+1}^{n}(2k + q − 2)(2k + q − 2j − 1)

= q 2^{2n−2j−q} \frac{(2j + q − 1)!}{j!(n − j)!(n + q)!} \frac{Γ(n + \frac{q}{2})Γ(n − j + \frac{q+1}{2})}{Γ(j + \frac{q}{2})Γ(\frac{q+1}{2})}.

Of course, these Γ–functions can always be written by factorials (or binomial coefficients), by distinguishing the cases q even and odd. Summarizing,

[z^{n}u^{j}]\frac{1}{(X + Y)^{q}} = q 2^{2n−2j−q} \frac{(2j + q − 1)!}{j!(n − j)!(n + q)!} \frac{Γ(n + \frac{q}{2})Γ(n − j + \frac{q+1}{2})}{Γ(j + \frac{q}{2})Γ(\frac{q+1}{2})}

or citing the cases q even and odd explicitly

[z^{n}u^{j}]\frac{1}{(X + Y)^{2p}} = \frac{2p(p − 1)!(j + 2p)!(2n − 2j + 2p − 1)!(2j + 2p − 1)!(n + p − 1)!}{2^{2p}(2p − 1)!(j + p − 1)!(n − j)!(n − j + p − 1)!j!(j + 2p)!(n + 2p)!},
[z^{n}u^{j}]\frac{1}{(X + Y)^{2p+1}} = \frac{(2p + 1)(j + p)!(2n + 2p − 1)!(n − j + p)!}{2^{2p}p!j!(n + p − 1)!(n − j)!(n + 2p + 1)!}.

Hence we have the following theorem.

Theorem 1. The s–th factorial moment 𝔼(X\underline{s} ; n,j) is given by the following explicit formula.

𝔼(X\underline{s} ; n,j) = \frac{s!}{B_{n}} ∑_{l=0}^{s} \binom{s}{l}(−1)^{s−l}4^{n−j} \frac{(l + 1) (2j + l)!}{j!(n − j)!(n + l + 1)!} \frac{Γ(n + \frac{l+1}{2})Γ(n + 1 − j + \frac{l}{2})}{Γ(j + \frac{l+1}{2})Γ(1 + \frac{l}{2})}.  (4)

With Stirling’s asymptotic formula for the factorials, we get for a fixed ratio ρ = j/n

\frac{(l + 1) (2j + l)!}{j!(n − j)!(n + l + 1)!} \frac{Γ(n + \frac{l+1}{2})Γ(n + 1 − j + \frac{l}{2})}{Γ(j + \frac{l+1}{2})Γ(1 + \frac{l}{2})} = 4^{ρn}n^{\frac{l−3}{2}} \frac{(1 − ρ)^{\frac{l}{2}} ρ^{\frac{l}{2}} 2^{l}(l + 1)}{\sqrt{π} Γ(1 + \frac{l}{2})} (1 + O(\frac{1}{n})) .

From this we see that the summand with l = s gives the main term in the asymptotic expansion of the factorial moments. Using the reflection law of the Gamma function we get

𝔼(X\underline{s} ; n,j) = \frac{(s + 1)!(1 − ρ)^{\frac{s}{2}} ρ^{\frac{s}{2}} 2^{s}}{Γ(1 + \frac{s}{2})} n^{\frac{s}{2}} + O (n^{\frac{s−1}{2}} ) = \frac{2}{\sqrt{π}} 4^{s}ρ^{\frac{s}{2}} (1 − ρ)^{\frac{s}{2}} Γ (\frac{s + 3}{2}) n^{\frac{s}{2}} + O (n^{\frac{s−1}{2}} ) .

Thus we have the following corollary.

Corollary 2. The s–th factorial moment 𝔼(X\underline{s} ; n,j) (and thus also the ordinary s–th moment 𝔼(X_{n,j}^{s})) is asymptotically for n → ∞ given by

𝔼(X\underline{s} ; n,j) = \frac{2}{\sqrt{π}} 4^{s}ρ^{\frac{s}{2}} (1 − ρ)^{\frac{s}{2}} Γ (\frac{s + 3}{2}) n^{\frac{s}{2}} + O (n^{\frac{s−1}{2}} )

Together with the theorem of Fréchet and Shohat (second central limit theorem) [1] and the fact, that the Maxwell distribution is uniquely determined by its moments, we get the following result, which was first proved in [4].

Corollary 3. The limiting distribution of the normalized height \frac{X_{n,j}}{\sqrt{n}} is for a fixed ratio ρ = \frac{j}{n} with

0 < ρ < 1 a Maxwell distribution with parameter σ = \sqrt{8ρ(1 − ρ)}. That means it has for x > 0 the density function

f_{ρ}(x) = \frac{x^{2}}{16\sqrt{π}(ρ(1 − ρ))^{\frac{3}{2}}} e^{− \frac{x^{2}}{16ρ(1−ρ)}} .  (5)

For the reader’s convenience we mention that the Maxwell distribution with parameter σ is defined as the distributions Y = \sqrt{X_{1}^{2} + X_{2}^{2} + X_{3}^{2}}, where the X_{i} are independently normally distributed random variables N (0, σ^{2}) with mean 0 and variance σ^{2}. It has the following density function f(x) and moments M_{s} = 𝔼(Y^{s})

f(x) = \frac{\sqrt{2}x^{2}}{\sqrt{π}σ^{3}} e^{− \frac{x^{2}}{2σ^{2}}} for x > 0 ; M_{s} = \frac{2}{\sqrt{π}} 2^{\frac{s}{2}} σ^{s}Γ (\frac{s + 3}{2}) .

3. t–ary trees

Let us consider t–ary trees for general t ≥ 2. In this instance, we can also report some progress, although the results are not so nice. The random variable X_{n,j} is again defined as the height of the leaf j in a t–ary tree of size n, where the leaves are labelled with the numbers 0, 1, …, (t − 1)n from left to right and all trees are equally likely.

Recall that the generating function of t–ary trees satisfies T (z) = 1 + zT^{t}(z), and that

T_{n} := [z^{n}]T (z) = \frac{1}{(t − 1)n + 1}\binom{tn}{n} and T_{n}^{(p)} := [z^{n}]T^{p}(z) = \frac{p}{(t − 1)n + p}\binom{tn + p − 1}{n},

which is classical and easy to see by means of Lagrange’s inversion formula: With T (z) = 1 + U(z) we get

[z^{n}]T^{p}(z) = [z^{n}](1 + U(z))^{p} = \frac{p}{n}[U^{n−1}](1 + U)^{tn+p−1} = \frac{p}{(t − 1)n + p}\binom{tn + p − 1}{n}.

The trivariate generating function

F (z, u, v) = ∑_{n,j,l} [Number of trees of size n with leaf j on level l]z^{n}u^{j}v^{l}

is now given by

F (z, u, v) = \frac{1}{1 − zv ∑_{k=0}^{t−1} u^{k} T^{t−1−k}(z) T^{k}(zu^{t−1})}.

Let us define the following abbreviations: X = T (z) and Y = T (zu^{t−1}) (in the previous section X and Y had a slightly different meaning). Now note that

z ∑_{k=0}^{t−1} u^{k}X^{t−1−k}Y^{k} = z \frac{X^{t} − u^{t}Y^{t}}{X − uY} = \frac{X − uY − (1 − u)}{X − uY} = 1 − \frac{1 − u}{X − uY}

so that we have

F (z, u, v) = \frac{1}{1 − v(1 − \frac{1−u}{X−uY} )}.  (6)

3.1. The Expectation. At first we want to find an explicit expression for the expectations 𝔼(X_{n,j}). Here Kirschenhofer writes [7]:

“For general t ≥ 2, the method, that led to an explicit expression for t = 2, is not feasible.”

Again, this statement is too pessimistic; in the following we will find an explicit formula for the expectations, from which it is also possible to get an asymptotic result without the laborious “diagonalization method,” by only using very elementary techniques.

Introducing

G_{1}(z, u) = \frac{∂}{∂v} F (z, u, v)|_{v=1}

we get by differentiating (6) w.r.t. v and evaluating at v = 1 the following result, which appeared in [5].

G_{1}(z, u) = (\frac{X − uY}{1 − u} )^{2} − \frac{X − uY}{1 − u} .

Extracting the coefficients for 0 ≤ j ≤ (t − 1)n leads immediately to

[z^{n}u^{j}]\frac{X − uY}{1 − u} = T_{n} and [z^{n}u^{j}] (\frac{X − uY}{1 − u} )^{2} = [z^{n}u^{j}]\frac{X^{2}}{(1 − u)^{2}} − 2[z^{n}u^{j}]\frac{XuY}{(1 − u)^{2}} .

For 0 ≤ j ≤ (t − 1)n we get then

[z^{n}u^{j}]\frac{X^{2}}{(1 − u)^{2}} = \frac{2(j + 1)}{(t − 1)n + 2}\binom{tn + 1}{n}

and

[z^{n}u^{j}]\frac{XuY}{(1 − u)^{2}} = ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\frac{1}{(t − 1)(n − k) + 1}\binom{t(n − k)}{n − k}(j − (t − 1)k).

Combining these results leads to

\begin{aligned}[z^{n}u^{j}] (\frac{X − uY}{1 − u} )^{2} & = \frac{2(j + 1)}{(t − 1)n + 2}\binom{tn + 1}{n} \\ & − 2 ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{j − (t − 1)k}{((t − 1)k + 1)((t − 1)(n − k) + 1)}\binom{tk}{k}\binom{t(n − k)}{n − k}. \end{aligned}  (7)

To get asymptotic equivalents it is helpful to manipulate this expression in the following way. Partial fraction expansion leads to

[z^{n}u^{j}] (\frac{X − uY}{1 − u} )^{2} = \frac{2(j + 1)}{(t − 1)n + 2}\binom{tn + 1}{n} − \frac{2(j + 1)}{(t − 1)n + 2} ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

+ \frac{2((t − 1)n − j + 1)}{(t − 1)n + 2} ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)(n − k) + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}.

In the following we use the identity

∑_{k=0}^{n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k} = \binom{tn + 1}{n} .

This is easy to prove, when considering the equation

(t − 1)zT′(z) + T (z) = ∑_{n≥0} \binom{tn}{n}z^{n}.

The sum can then be simplified by extracting the coefficients of a convolution of two functions:

∑_{k=0}^{n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k} = [z^{n}] T (z) ((t − 1)zT′(z) + T (z))

= [z^{n}] T^{2}(z) + \frac{t − 1}{2}[z^{n−1}] (T^{2}(z))′ = (1 + \frac{t − 1}{2}n) [z^{n}] T^{2}(z) = \binom{tn + 1}{n}.

When the first sum is running over the whole range from 0 to n it cancels the extra summand, which is asymptotically of higher order. Adding the remaining summands leads to the following expression

[z^{n}u^{j}] (\frac{X − uY}{1 − u} )^{2} = \frac{2(j + 1)}{(t − 1)n + 2} ∑_{⌊\frac{j−1}{t−1}⌋+1≤k≤n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

+ \frac{2((t − 1)n − j + 1)}{(t − 1)n + 2} ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)(n − k) + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}.

This leads to the following exact formula for the expectation 𝔼 (X_{n,j}) = \frac{1}{T_{n}} [z^{n}u^{j}] G_{1}(z, u).

Theorem 4. The expectation 𝔼 (X_{n,j}) of the height of leaf j in a t–ary tree with n internal nodes is given by

\begin{matrix}𝔼 (X_{n,j}) = \frac{2 (j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{⌊\frac{j−1}{t−1}⌋+1≤k≤n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k} \\ + \frac{2 ((t − 1)n − j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)(n − k) + 1}\binom{tk}{k}\binom{t(n − k)}{n − k} − 1 . \end{matrix}  (8)

In the following we will obtain an asymptotic equivalent of this expression. First we want to evaluate the sum

\frac{2 (j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{⌊\frac{j−1}{t−1}⌋+1≤k≤n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

asymptotically for a fixed ratio ρ = \frac{j}{(t−1)n}. With Stirling’s asymptotic formula for the binomial coefficients

\binom{tn}{n} = \begin{matrix}\sqrt{t} & (\frac{t^{t}}{(t−1)^{t−1}} ) & n \\ \sqrt{t − 1} & \sqrt{2} & \sqrt{π} \end{matrix} n^{− \frac{1}{2}} (1 + O(\frac{1}{n}))

we obtain the following expansion for the summands from k = ρn to n − 1;

\frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

= \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{1}{\sqrt{k}\sqrt{n − k}} (1 + O(\frac{1}{k} )) (1 + O(\frac{1}{n − k} ))

= \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{1}{\sqrt{k}\sqrt{n − k}} + \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{c_{t}}{\sqrt{k}(n − k)^{\frac{3}{2}}} .

In the last expression, the constant c_{t} is independent from k and n.

Therefore we get

\frac{2 (j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{⌊\frac{j−1}{t−1}⌋+1≤k≤n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

= ∑_{k=ρn}^{n−1} \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{1}{\sqrt{k}\sqrt{n − k}}

+ ∑_{k=ρn}^{n−1} \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{c_{t}}{\sqrt{k}(n − k)^{\frac{3}{2}}} + O(1).

Interpreting the first sum as a Riemann sum, we obtain the following expansion;

\frac{2(j + 1)((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{k=ρn}^{n−1} \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{1}{\sqrt{k}\sqrt{n − k}}

= \frac{\sqrt{2}\sqrt{t}ρ\sqrt{n}}{\sqrt{π}\sqrt{t − 1}} ∑_{\frac{k}{n} =ρ}^{1− \frac{1}{n}} \frac{1}{n (\frac{k}{n})^{\frac{3}{2}} \sqrt{1 − \frac{k}{n}}} (1 + O(\frac{1}{n})) = \frac{\sqrt{2}\sqrt{t}ρ\sqrt{n}}{\sqrt{π}\sqrt{t − 1}} ∫_{x=ρ}^{1} \frac{dx}{x^{\frac{3}{2}} \sqrt{1 − x}} + O(1)

= \frac{\sqrt{2}\sqrt{t}ρ\sqrt{n}}{\sqrt{π}\sqrt{t − 1}} (−\frac{2\sqrt{1 − x}}{\sqrt{x}} )|_{x=ρ}^{1} + O(1) = \frac{2\sqrt{2}\sqrt{t}\sqrt{ρ}\sqrt{1 − ρ}}{\sqrt{π}\sqrt{t − 1}}\sqrt{n} + O(1).

The remainder term leads to the following order estimation;

\frac{2(j + 1)((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{k=ρn}^{n−1} \frac{t}{2π(t − 1)} (\frac{t^{t}}{(t − 1)^{t−1}} )^{n} \frac{1}{(t − 1)k + 1} \frac{c_{t}}{\sqrt{k}(n − k)^{\frac{3}{2}}}

= cn^{\frac{3}{2}} ∑_{k=ρn}^{n−1} \frac{1}{k^{\frac{3}{2}} (n − k)^{\frac{3}{2}}} = c ∑_{k=ρn}^{n−1} (\frac{1}{k} + \frac{1}{n − k} )^{\frac{3}{2}} ≤ 2c ∑_{k=1}^{\frac{n}{2}} (\frac{1}{k} + \frac{1}{n − k} )^{\frac{3}{2}} ≤ 2c ∑_{k=1}^{\frac{n}{2}} (\frac{1}{k} + \frac{2}{n})^{\frac{3}{2}}

≤ 2c ∑_{k=1}^{\frac{n}{2}} (\frac{2}{k} )^{\frac{3}{2}} = O(1).

So we have the asymptotic expansion

\frac{2 (j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{⌊\frac{j−1}{t−1}⌋+1≤k≤n} \frac{1}{(t − 1)k + 1}\binom{tk}{k}\binom{t(n − k)}{n − k} = \frac{2\sqrt{2}\sqrt{t}\sqrt{ρ}\sqrt{1 − ρ}}{\sqrt{π}\sqrt{t − 1}}\sqrt{n} + O(1).

An analogous procedure leads to

\frac{2 ((t − 1)n − j + 1) ((t − 1)n + 1)}{((t − 1)n + 2)\binom{tn}{n}} ∑_{0≤k≤⌊\frac{j−1}{t−1}⌋} \frac{1}{(t − 1)(n − k) + 1}\binom{tk}{k}\binom{t(n − k)}{n − k}

= \frac{2\sqrt{2}\sqrt{t}\sqrt{ρ}\sqrt{1 − ρ}}{\sqrt{π}\sqrt{t − 1}}\sqrt{n} + O(1).

So we get finally the asymptotic result for the expectations of the leaf heights in t–ary trees, as it was stated in [7]. Theorem 5. The expectation 𝔼 (X_{n,j}) of the height of the leaf j in a t–ary tree with n internal nodes is asymptotically for a fixed ratio ρ = \frac{j}{(t−1)n} with 0 < ρ < 1 for n → ∞ given as

𝔼 (X_{n,j}) = \frac{4\sqrt{2}\sqrt{t}\sqrt{ρ}\sqrt{1 − ρ}}{\sqrt{π}\sqrt{t − 1}}\sqrt{n} + O(1).  (9)

3.2. Higher Moments. We are also able to find explicit expressions for the higher factorial moments, although they are not so nice.

Differentiating F (z, u, v) s-times w.r.t. v and evaluating at v = 1 leads to

\frac{∂^{s}}{∂v^{s}} F (z, u, v)|_{v=1} = \frac{s!(1 − \frac{1−u}{X−uY} )^{s}}{(\frac{1−u}{X−uY} )s+1} = ∑_{p=1}^{s+1}(−1)^{s+1−p}s!\binom{s}{p − 1} (\frac{X − uY}{1 − u} )^{p} .

The coefficients from (\frac{X−uY}{1−u} )^{p} are obtained as follows.

[z^{n}u^{j}] (\frac{X − uY}{1 − u} )^{p} = ∑_{l=0}^{p}[z^{n}u^{j}](−1)^{l}\binom{p}{l}\frac{(uY)^{l}X^{p−l}}{(1 − u)^{p}}

= T_{n}^{(p)}\binom{j + p − 1}{p − 1} + ∑_{l=1}^{p−1}(−1)^{l}\binom{p}{l} ∑_{0≤k≤⌊\frac{j−l}{t−1}⌋} T_{k}^{(l)} T_{n−k}^{(p−l)}\binom{j − l − (t − 1)k + p − 1}{p − 1}.

Therefore we get

\frac{∂^{s}}{∂v^{s}} F (z, u, v)|_{v=1} = ∑_{p=1}^{s+1}(−1)^{s+1−p}s!\binom{s}{p − 1}[T_{n}^{(p)}\binom{j + p − 1}{p − 1}

+ ∑_{l=1}^{p−1}(−1)^{l}\binom{p}{l} ∑_{0≤k≤⌊\frac{j−l}{t−1}⌋} T_{k}^{(l)} T_{n−k}^{(p−l)}\binom{j − l − (t − 1)k + p − 1}{p − 1}].

Hence the higher moments are given by the following theorem. Theorem 6. The s–th factorial moment 𝔼(X\underline{s} ; n,j) of the height of the leaf j in a t–ary tree with n internal nodes is given by

\begin{aligned}𝔼(X\underline{s} ; n,j) & = \frac{1}{T_{n}} ∑_{p=1}^{s+1}(−1)^{s+1−p}s!\binom{s}{p − 1}[T_{n}^{(p)}\binom{j + p − 1}{p − 1} \\ & + ∑_{l=1}^{p−1}(−1)^{l}\binom{p}{l} ∑_{0≤k≤⌊\frac{j−l}{t−1}⌋} T_{k}^{(l)} T_{n−k}^{(p−l)}\binom{j − l − (t − 1)k + p − 1}{p − 1}]. \end{aligned}  (10)

One could work out the asymptotics from this formula, at least for the variance, but the computational effort would be considerable, because of the alternating sign in the inner sum. Since according formulæ are already stated in [3], we refrain from doing that.

References

[1] M. Fisz. Probability Theory and Mathematical Statistics. John Wiley, 1963.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[3] W. Gutjahr. The variance of level numbers in certain families of trees. Random Structures and Algorithms, 3:361–374, 1992.

[4] W. Gutjahr and G. Pflug. The asymptotic distribution of leaf heights in binary trees. Graphs and Combinatorics, 8:243–251, 1992.

[5] P. Kirschenhofer. On the height of leaves in binary trees. Journal of Combinatorics, Information and System Sciences, 8:44 –60, 1983.

[6] P. Kirschenhofer. Some new results on the average height of binary trees. Ars Combinatoria, 16 A:255–260, 1983.

[7] P. Kirschenhofer. Asymptotische Untersuchungen zur durchschnittlichen Gestalt gewisser Graphenklassen. In E. Hlawka, editor, Zahlentheoretische Analysis, volume 1114 of Lecture Notes in Mathematics, pages 40–54, 1985.

[8] A. Panholzer and H. Prodinger. Descendants and ascendants in binary trees. Discrete Mathematics and Theoretical Computer Science, 1:247–266, 1997.

[9] M. Petkovšek, H. Wilf, and D. Zeilberger. A = B. A.K. Peters, Ltd., 1996.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

   E-mail address: e9125354@fbma.tuwien.ac.at (Alois Panholzer)
   E-mail address: Helmut.Prodinger@tuwien.ac.at
   WWW-address: http://info.tuwien.ac.at/theoinf/proding.htm