ON A PROBLEM OF YEKUTIELI AND MANDELBROT ABOUT THE BIFURCATION RATIO OF BINARY TREES^{∗}

HELMUT PRODINGER

Abstract. Concerning the Horton–Strahler number (or Register function) of binary trees, Yekutieli and Mandelbrot posed the problem of analyzing the bifurcation ratio of the root, which means how many maximal subtrees of register function one less than the whole tree are present in the tree. We show, that if all binary trees of size n are considered to be equally likely, than the average value of this number of subtrees is asymptotic to 3.341266+δ(log_{4} n), where an analytic expression for the numerical constant is available and δ(x) is a (small) periodic function of period 1, which is also given explicitly. Additionally, we sketch the computation of the variance and also of higher bifurcation ratios.

1. Introduction

This paper solves a problem that was left open (and attacked empirically) in [16]. It concerns binary trees and Horton–Strahler orderings. Here, we phrase everything in the equivalent notion of the register function. The register function became famous among computer scientists in the late seventies when Flajolet and his team and Kemp independently determined the average number of registers needed to evaluate a binary tree of size n [5, 9, 10, 3].

If we have an extended binary tree, we label the leaves with 0, and, recursively, if the left subtree of a node is labeled with a and the right subtree with b, we label the node with max{a, b} if a ≠ b and with a + 1 otherwise. The value attached to the root is called the register function of the tree t. The value attached to a particular node is the register function of the subtree having this node as its root.

The authors in [16] consider the bifurcation ratio (at the root), which we will call the YM–parameter throughout. It is meant to be the number of maximal subtrees (which is not the same as the number of internal nodes (!)) having register function exactly 1 less than the register function of the entire tree. See the original paper for a more elaborated problem statement and some motivation. Figure 1 lists all 5 trees with 3 nodes. The first tree in this list has YM–parameter 2, and the other four trees have YM–parameter 4. Hence, the average value of the YM–parameter is 18/5 in this instance. The tree in Figure 2 has YM–parameter 3.

It was observed empirically that the expected value of this parameter is asymptotically a periodic function of log_{4} n if all trees of size n (n internal nodes) are considered to be equally likely. Here we want to settle this problem by explicitly describing the periodic function in terms of the Fourier coefficients. In principle, a full asymptotic expansion could be given, but the computation of the lower order term becomes more and more complicated.

Date: April 26, 1996.

∗ A preliminary version of this paper was presented at the conference Latin 95 ([14]).

[figure: 0; 0; 1; 0; 0; 1; 2; 0; 0; 1; 1; 1; 0; 0; 0; 0; 1; 1; 1; 0; 0; 1; 0; 0; 0; 1; 1; 0; 1; 0; 0; 0; 1; 1; 0]

Figure 1. All 5 trees with 3 internal nodes

[figure: 0; 0; 1; 0; 0; 1; 0; 0; 1; 0; 0; 2; 2; 0; 0; 1; 0; 0; 1; 2; 0; 0; 0; 0; 1; 3; 2; 1; 3; 1; 3]

Figure 2. A binary tree of size 15 with register function 3 and 3 maximal subtrees with register function 2, which are displayed in Figure 3.

2. The average value of the Yekutieli–Mandelbrot parameter

We start our analysis with some notions and results from the literature. Let b_{n}, r_{p,n}, and s_{p,n} denote the number of binary trees of size n, the number of binary trees of size n and register function = p, and the number of binary trees of size n, and register function ≥ p, respectively. Then

[figure: 0; 0; 1; 0; 0; 1; 0; 0; 1; 0; 0; 2; 2; 0; 0; 1; 0; 0; 1; 2; 0; 0; 2; 1; 1]

Figure 3. The 3 maximal subtrees with register function 2.

B(z) = ∑_{n≥0} b_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} = ∑_{n≥0} \frac{1}{n + 1}\binom{2n}{n}z^{n} = 1 + u, with z = \frac{u}{(1 + u)^{2}}

R_{p}(z) = ∑_{n≥0} r_{p,n}z^{n} = \frac{1 − u^{2}}{u} \frac{u^{2^{p}}}{1 − u^{2^{p+1}}} , with z = \frac{u}{(1 + u)^{2}} ,

S_{p}(z) = ∑_{n≥0} s_{p,n}z^{n} = \frac{1 − u^{2}}{u} \frac{u^{2^{p}}}{1 − u^{2^{p}}} , with z = \frac{u}{(1 + u)^{2}} .

(1)

The first generating function is classical, and the other two appeared in [5, 9, 11, 12, 13]. The substitution (cf. [2]) z = u/(1 + u)^{2} will be used throughout. Note that B(z) − S_{p}(z) is the generating function of the binary trees with n nodes and register function < p.

Now, let w_{p,k,n} be the number of binary trees with n nodes, register function p, and YM–parameter k, and let

W_{p}(z, y) = ∑_{n,k≥0} w_{p,k,n} y^{k}z^{n}  (2)

be its bivariate generating function.

To find the expected values, we have to work with T_{p}(z) = \frac{∂}{∂y} W_{p}(z, y)|_{y=1} and

T (z) = ∑_{p≥1} T_{p}(z).  (3)

The coefficient of z^{n} in T (z), divided by \frac{1}{n+1} \binom{2n}{n}, is the expected value sought by Yekutieli and Mandelbrot.

We can find an equation for W_{p}(z, y) by considering 3 cases. Either both subtrees have register function p − 1, then we have y^{2}, since the YM–parameter is 2. Or, we have to go down recursively. If the smaller subtree (with respect to the register function!) of the root has register function p − 1, we have to label by a y, if it is even smaller, we do not label. Observe that there is a unique path from the root to a node with both successors having register function p − 1. Hence we have for p ≥ 1

W_{p}(z, y) = zy^{2}R_{p−1}^{2}(z) + 2zyW_{p}(z, y)R_{p−1}(z) + 2zW_{p}(z, y)(B(z) − S_{p−1}(z)),  (4)

4 HELMUT PRODINGER

and therefore (since R_{p−1}(z) + B(z) − S_{p−1}(z) = B(z) − S_{p}(z))

T_{p}(z) = 2zR_{p−1}^{2}(z) + 2zR_{p}(z)R_{p−1}(z) + 2zT_{p}(z)(B(z) − S_{p}(z)),

or

T_{p}(z) = \frac{2zR_{p−1}(z)(R_{p−1}(z) + R_{p}(z))}{1 − 2z(B(z) − S_{p}(z))}.  (5)

One may now use the definitions (1) to easily verify

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

Therefore (5) may be rewritten as

\begin{aligned}T_{p}(z) & = \frac{1 + u}{1 − u} \frac{1 − u^{2^{p}}}{1 + u^{2^{p}}} \frac{2u}{(1 + u)^{2}} (\frac{1 − u^{2}}{u} )^{2} \frac{u^{2^{p−1}}}{1 − u^{2^{p}}} [\frac{u^{2^{p−1}}}{1 − u^{2^{p}}} + \frac{u^{2^{p}}}{1 − u^{2^{p+1}}} ] \\ & = 2\frac{1 − u^{2}}{u} [\frac{u^{2^{p}}}{1 − u^{2^{p+1}}} + \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})(1 − u^{2^{p+1}})}] . \end{aligned}  (6)

Hence we get, upon summing on p and performing some easy simplifications,

\begin{aligned}T (z) & = 2\frac{1 − u^{2}}{u} ∑_{p≥1} [\frac{u^{2^{p}}}{1 − u^{2^{p+1}}} + \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})(1 − u^{2^{p+1}})}] \\ & = 2\frac{1 − u^{2}}{u} [\frac{u^{2}}{1 − u^{2}} + ∑_{p≥1} \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})(1 − u^{2^{p+1}})}] \\ & = 2u + 2\frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})^{2}(1 − u^{2^{p}})}. \end{aligned}  (7)

Let us concentrate on the series

σ = ∑_{p≥1} \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})^{2}(1 − u^{2^{p}})} = ∑_{p≥1, i,j≥0} u^{3·2^{p−1}+(i+j)2^{p}}(−1)^{i}(i + 1)  (8)

appearing in (7), since the other terms in (7) are easy. Now

∑_{i=0}^{k}(−1)^{i}(i + 1) = (−1)^{k} (⌊\frac{k}{2} ⌋ + 1) ,

and thus

\begin{aligned}σ & = ∑_{p≥0,k≥0} u^{3·2^{p}+k2^{p+1}}(−1)^{k} (⌊\frac{k}{2} ⌋ + 1) \\ & = ∑_{p≥0,k≥1} u^{2^{p}(2k+1)}(−1)^{k−1} ⌊\frac{k+1}{2}⌋ \\ & = − ∑_{p,k≥0} ku^{2^{p}(4k+1)} + ∑_{p,k≥0}(k + 1)u^{2^{p}(4k+3)}. \end{aligned}  (9)

The further methodology is to find the behavior of T (z(u)) as u → 1, itself giving the local expansion of T (z) about the singularity z = \frac{1}{4}. Since elementary methods fail, we proceed as follows. Setting u = e^{−t}, we are interested in t → 0. As it is now standard, and described in [6, 7, 13], we compute the Mellin transform (see the survey [4]) of the series

σ = − ∑_{p,k≥0} ke^{−t2^{p}(4k+1)} + ∑_{p,k≥0}(k + 1)e^{−t2^{p}(4k+3)}.

Since e^{−at} maps into a^{−s}Γ(s), σ maps into Γ(s) times

− ∑_{p,k≥0} k2^{−ps}(4k + 1)^{−s} + ∑_{p,k≥0}(k + 1)2^{−ps}(4k + 3)^{−s}.

These series are easily evaluated by means of the Hurwitz zeta function ([15])

ζ(s, a) = ∑_{n≥0} \frac{1}{(n + a)^{s}} .

We just mention that the so-called fundamental strip is ⟨2, ∞⟩. We find

∑_{k≥0} k(4k + 1)^{−s} = 4^{−s} ∑_{k≥0} k(k + \frac{1}{4})^{−s} = 4^{−s} (ζ(s − 1, \frac{1}{4}) − \frac{1}{4}ζ(s, \frac{1}{4}))

and

∑_{k≥0}(k + 1)(4k + 3)^{−s} = 4^{−s} ∑_{k≥0}(k + 1)(k + \frac{3}{4})^{−s} = 4^{−s} (ζ(s − 1, \frac{3}{4}) + \frac{1}{4}ζ(s, \frac{3}{4})) .

Also,

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

Hence σ maps into

\begin{matrix}\frac{Γ(s)}{1 − 2^{−s}} & [−4^{−s} (ζ(s − 1, \frac{1}{4}) − ζ(s − 1, \frac{3}{4})) + \frac{1}{4}(1 − 2^{−s})ζ(s)] \\ = −\frac{Γ(s)}{2^{s}(2^{s} − 1)} (ζ(s − 1, \frac{1}{4}) − ζ(s − 1, \frac{3}{4})) + \frac{1}{4}Γ(s)ζ(s). \end{matrix}  (10)

To find the asymptotic behavior of σ, we must consider the residues of the last quantity times t^{−s} left to the line ℜs = \frac{5}{2}. As already stated, more information about this methodology can be found in [6, 7, 11, 12, 13].

The Hurwitz zeta functions have simple poles at s = 2, but they cancel out. The zeta function has a simple pole at s = 1, and the corresponding residue is \frac{1}{4t}. At s = 0, at the first glance, it looks like a second order pole. However, according to [15], we have the following. Write β(s) = ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4}), then

β(s) = 4(8π)^{s−1}Γ(1 − s) cos \frac{sπ}{2} β(1 − s).  (11)

The presence of the cosine gives the value β(−1) = 0. We also need β′(−1). Deriving the product, only the term with the cosine derived survives, and we find

β′(−1) = \frac{1}{32π} β(2).

The series

C = ∑_{k≥0} \frac{(−1)^{k}}{(2k + 1)^{2}} = \frac{1}{16}β(2) = 0.9159655942 …  (12)

is called Catalan’s constant [1]. Hence as s → 0, β(s − 1) ∼ s · \frac{C}{2π}.

Therefore the corresponding residue is

−\frac{1}{log 2} \frac{C}{2π} − \frac{1}{8}.

There are also simple poles at s = χ_{k} = \frac{2kπi}{log 2} (k ≠ 0) with residue

−\frac{Γ(χ_{k})}{log 2}β(χ_{k} − 1)t^{−χ_{k}}.

The other residues at the negative integers (originating from the Γ–function) lead to smaller order terms and will be neglected.

Therefore the contribution of the series σ is

\frac{1}{4t} − \frac{1}{log 2} \frac{C}{2π} − \frac{1}{8} − \frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})β(χ_{k} − 1)t^{−χ_{k}}  (13)

Let us recall that we want the expansion of T (z) in terms of 1−4z. First, we give it in terms of t (t → 0).

T (z) ∼ 2 − 2t + 4t [\frac{1}{4t} − \frac{1}{log 2} \frac{C}{2π} − \frac{1}{8} − \frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})β(χ_{k} − 1)t^{−χ_{k}} ] .  (14)

And, since

t ∼ 2\sqrt{1 − 4z},

we obtain

T (z) ∼ 3 − (\frac{4C}{(log 2)π} + 5) \sqrt{1 − 4z} − \frac{8}{log 2} ∑_{k≠0} Γ(χ_{k})β(χ_{k} − 1)(1 − 4z)^{(1−χ_{k})/2}. (15)

Now, according to [7], we can go over to the asymptotics of the coefficients, using the rule

[z^{n}](1 − z)^{α} ∼ \frac{n^{−α−1}}{Γ(−α)} .

For the sake of simplicity, we stated all the asymptotic expansions in terms of ‘∼’ (asymptotic equivalence). However, in all instances, O–terms are available (decreasing the readability), and a “O–transfer”[7] is possible; we only state a O–result in our main theorem. In this way we get

[z^{n}]T (z) ∼ \frac{1}{2\sqrt{π}} (\frac{4C}{(log 2)π} + 5) 4^{n}n^{−3/2}

− \frac{2}{(log 2)\sqrt{π}} ∑_{k≠0}(χ_{k} − 1)Γ(\frac{χ_{k}}{2} )β(χ_{k} − 1)4^{n}n^{−3/2}e^{log_{4} n·2kπi} .

(16)

Since

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

we get the desired result by dividing these two quantities.

The value

\frac{2C}{(log 2)π} + \frac{5}{2} = 3.341266 …

is the value around which the expected value of the YM–parameter fluctuates, in agreement with the numerical observations in [16].

Theorem 1. The average value of the Yekutieli–Mandelbrot parameter, if all binary trees of size n are considered to be equally likely, is given by

\frac{2C}{(log 2)π} + \frac{5}{2} + δ(log_{4} n) + O(\frac{1}{n}).  (17)

The periodic function δ(x) has mean value 0 and admits the following representation as a Fourier series,

δ(x) = −\frac{2}{log 2} ∑_{k≠0}(χ_{k} − 1)Γ(\frac{χ_{k}}{2} )β(χ_{k} − 1)e^{2kπix};  (18)

the function β(x) is defined in (11) and χ_{k} = \frac{2kπi}{log 2}.

Remark . Although it is not needed for the solution of the present problem, it is possible to get an exact formula for [z^{n}]T (z). For that, we use Cauchy’s integral formula.

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

= 2 · \frac{1}{2πi} ∮ \frac{du(1 − u)(1 + u)^{2n−1}}{u^{n+1}} [u + \frac{1 − u^{2}}{u} σ]

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

= 2\binom{2n − 1}{n − 1} − 2\binom{2n − 1}{n − 2} + 2[u^{n+1}](1 − u)^{2}(1 + u)^{2n}σ

= \frac{2}{n + 1}\binom{2n}{n} + 2([u^{n+1}] − 2[u^{n}] + [u^{n−1}])(1 + u)^{2n} ∑_{m≥1} ψ(m)u^{m},

where the arithmetical function ψ(m) is defined by

ψ(m) = \begin{cases}−k & if m = 2^{i}(4k + 1) for some i and k \\ k + 1 & if m = 2^{i}(4k + 3) for some i and k \end{cases}  (19)

for convenience. Note that each integer has a unique representation as 2^{i}(4k+1) or 2^{i}(4k+3). Hence (apart from a normalization factor \frac{1}{n+1} \binom{2n}{n} ) an exact value of the expected value of the YM–parameter in an n–node binary tree is

[z^{n}]T (z) = \frac{2}{n + 1}\binom{2n}{n} + 2 ∑_{m≥1} ψ(m) [\binom{2n}{n + 1 − m} − 2\binom{2n}{n − m} + \binom{2n}{n − 1 − m}] .(20)

One could also work out the asymptotics from this formula, but it is less recommended because of more involved computations.

8 HELMUT PRODINGER

3. The variance

The variance can be analyzed in the same style. We give the key steps.

Let U_{p}(z) = \frac{∂^{2}}{∂y^{2}} W_{p}(z, y)|_{y=1} be the second factorial moment. We find from the basic recursion (2)

\begin{aligned}U_{p}(z) & = \frac{2zR_{p−1}^{2}(z) + 4zT_{p}(z)R_{p−1}(z)}{1 − 2z(B(z) − S_{p}(z))} \\ & = 2\frac{1 − u^{2}}{u} [\frac{u^{2^{p}}}{1 − u^{2^{p+1}}} + 4\frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})^{2}(1 − u^{2^{p}})} + 4\frac{u^{2^{p+1}}}{(1 + u^{2^{p}})^{3}(1 − u^{2^{p}})}] , \end{aligned} (21)

and

U(z) := ∑_{p≥1} U_{p}(z) = 2u + 8\frac{1 − u^{2}}{u} σ + 8\frac{1 − u^{2}}{u} τ − 8\frac{u}{(1 + u)^{2}}  (22)

with

τ := ∑_{p≥0} \frac{u^{2^{p+1}}}{(1 + u^{2^{p}})^{3}(1 − u^{2^{p}})}.  (23)

We compute

\begin{aligned}τ & = ∑_{p,i,j≥0} u^{2^{p}(2+i+j)}\binom{−3}{i} \\ & = ∑_{p,k≥0} u^{2^{p}(k+2)}(−1)^{k} ⌊\frac{k+2}{2}⌋ ⌊\frac{k+3}{2}⌋ \\ & = ∑_{p,k≥0} u^{2^{p}k}(−1)^{k} ⌊\frac{k}{2} ⌋ ⌊\frac{k+1}{2}⌋ \\ & = ∑_{p,k≥1} u^{2^{p}k}k^{2} − ∑_{p,k≥0} u^{2^{p}(2k+1)}k(k + 1) \\ & =: σ_{1} − σ_{2} \end{aligned}  (24)

We set u = e^{−t} and compute the Mellin transform of σ_{1};

\frac{Γ(s)}{2^{s} − 1}ζ(s − 2)

and of σ_{2};

Γ(s)ζ(s − 2)\frac{2^{s−2} − 1}{2^{s} − 1} − \frac{1}{4}Γ(s)ζ(s),

so that τ maps into

2Γ(s)ζ(s − 2)\frac{1 − 2^{s−3}}{2^{s} − 1} + \frac{1}{4}Γ(s)ζ(s).

We must find the residues of this times t^{−s}, which yields, apart from the fluctuating terms

∼ \frac{1}{4t} + \frac{7ζ′(−2)}{4 log 2} − \frac{1}{8}.  (25)

Inserting this into (22) and using the results about σ, we are led to the local expansion of U(z) (no fluctations are given);

U(z) ∼ 8 − (12 + \frac{16C}{(log 2)π} − \frac{56ζ′(−2)}{log 2}) \sqrt{1 − 4z}  (26)

To get the “mean” of the fluctuating function we have to take the coefficient of \sqrt{1 − 4z} and divide it by −2, which gives a numerical value 10.595047 . . ..

This is consistent with explicit computations performed with Maple: For that, we computed the first 10 values of W_{p}(z, y) and differentiated this function twice w.r.t. y, followed by y = 1. The resulting function was expanded as a series in z, and for instance, the coefficient of z^{30}, divided by the 30–th Catalan number b_{30}, gives a value 11.2763828; a similar computation gives 3.263013186 in the instance of the expectation (again n = 30).

The fluctuations are not too small in amplitude (usually, in the “register” context, they are of the order 10^{−2}, which originates from χ_{1}/2 = πi/ log 2 and the value of the Γ– function at this point, see [5]); however, with the first few Fourier coefficients, they could be approximated very well. Since this was only the second factorial moment, we have to add the expectation (mean term) 3.341266 … and subtract the square of it. The resulting numerical value is 2.7722547 . . .. This does not match with the plot in [16], and we are not able to reproduce the computations done in this paper. One should furthermore be aware of the fact that, when squaring the expectation, the square of the periodic function δ(x) which is involved does no longer have mean zero. Since this function is not too small in amplitude, the numerical value 2.7722547 … is not too meaningful either. Since we find it difficult to get explicit numerical values for the Fourier coefficients of δ^{2}(x), we do not pursue this further.

4. Higher bifurcation rates

This section indicates that the machinery used in the previous sections to deal with the original YM–parameter is powerful enough to deal with more general situations (higher bifurcation rates). Since the necessary computations become quite messy, we confine ourselves with a sketch of the key steps of one particular case.

We want to count into how many maximal subtrees of register function p − 2 the maximal subtrees of register function p − 1 bifurcate, if the whole tree has register function p for some p. In the example of Figure 1, only the first tree contributes 4, and the other ones 0. For the tree in Figure 2, the value is 7, which might be seen more easily from Figure 3. To formulate it differently, this parameter counts the number of maximal subtrees of register function 2 less than the whole tree.

We can use essentially the same decomposition as in the earlier case. Let us label all those maximal subtrees of register function p − 2 by the variable y and use (as an ad hoc notation) the generating function D_{p}(z, y). We obtain (for p ≥ 2)

D_{p}(z, y) = zW_{p−1}^{2}(z, y) + 2zD_{p}(z, y)W_{p−1}(z, y) + 2zD_{p}(z, y)(B(z) − S_{p−1}(z)). (27)

Set T_{p}^{(2)}(z) = \frac{∂}{∂y} D_{p}(z, y)|_{y=1}, then we get

T_{p}^{(2)}(z) = 2zT_{p−1}(z)\frac{R_{p−1}(z) + R_{p}(z)}{1 − 2z(B(z) − S_{p}(z))}.  (28)

10 HELMUT PRODINGER

We computed already that (cf. (5) and (6) )

2z \frac{R_{p−1}(z) + R_{p}(z)}{1 − 2z(B(z) − S_{p}(z))} = 2u^{2^{p−1}} \frac{1 + u^{2^{p−1}} + u^{2^{p}}}{(1 + u^{2^{p}})^{2}}

and

T_{p}(z) = \frac{2(1 − u^{2})}{u} \frac{u^{2^{p}}(1 − u^{2^{p}})(1 + u^{2^{p−1}} + u^{2^{p}})}{(1 − u^{2^{p+1}})^{2}}.

Therefore

T_{p}^{(2)}(z) = \frac{4(1 − u^{2})}{u} \frac{u^{2^{p}}(1 − u^{3·2^{p−1}})(1 + u^{2^{p−2}} + u^{2^{p−1}})}{(1 − u^{2^{p+1}})^{2}}  (29)

and

T^{(2)}(z) := ∑_{p≥2} T_{p}^{(2)}(z) = \frac{4(1 − u^{2})}{u} ∑_{p≥0} \frac{u^{2^{p+2}}(1 − u^{3·2^{p+1}})(1 + u^{2^{p}} + u^{2^{p+1}})}{(1 − u^{2^{p+3}})^{2}}.  (30)

Let us forget about the factor \frac{4(1−u^{2})}{u} for the moment and set u = e^{−t} in the remaining sum σ^{(2)}. Its Mellin transform is

\frac{1}{1 − 2^{−s}}

times the Mellin transform of

\frac{e^{−4t}(1 − e^{−6t})(1 + e^{−t} + e^{−2t})}{(1 − e^{−8t})^{2}} = ∑_{k≥0}(k + 1)e^{−8kt}e^{−4t}(1 − e^{−6t})(1 + e^{−t} + e^{−2t}),

which is

Γ(s) ∑_{k≥0}(k + 1) (\frac{1}{(8k + 4)^{s}} + \frac{1}{(8k + 5)^{s}} + \frac{1}{(8k + 6)^{s}}

−\frac{1}{(8k + 10)^{s}} − \frac{1}{(8k + 11)^{s}} − \frac{1}{(8k + 12)^{s}} )

= \frac{Γ(s)}{8^{s}} ∑_{k≥0}(k + 1) (\frac{1}{(k + \frac{1}{2})^{s}} + \frac{1}{(k + \frac{5}{8})^{s}} + \frac{1}{(k + \frac{3}{4})^{s}} )

− \frac{Γ(s)}{8^{s}} ∑_{k≥0} k (\frac{1}{(k + \frac{1}{4})^{s}} + \frac{1}{(k + \frac{3}{8})^{s}} + \frac{1}{(k + \frac{1}{2})^{s}} )

= \frac{Γ(s)}{8^{s}}( − ζ(s − 1, \frac{1}{4}) + ζ(s − 1, \frac{3}{4}) − ζ(s − 1, \frac{3}{8}) + ζ(s − 1, \frac{5}{8})

+ ζ(s, \frac{1}{2}) + \frac{1}{4}ζ(s, \frac{1}{4}) + \frac{1}{4}ζ(s, \frac{3}{4}) + \frac{3}{8}ζ(s, \frac{3}{8}) + \frac{3}{8}ζ(s, \frac{5}{8})) .

Altogether the Mellin transform of the sum σ^{(2)} is

\begin{aligned}\frac{Γ(s)}{8^{s}(1 − 2^{−s})}( & − ζ(s − 1, \frac{1}{4}) + ζ(s − 1, \frac{3}{4}) − ζ(s − 1, \frac{3}{8}) + ζ(s − 1, \frac{5}{8}) \\ & + ζ(s, \frac{1}{2}) + \frac{1}{4}ζ(s, \frac{1}{4}) + \frac{1}{4}ζ(s, \frac{3}{4}) + \frac{3}{8}ζ(s, \frac{3}{8}) + \frac{3}{8}ζ(s, \frac{5}{8})), \end{aligned}  (31)

and we have to find the residues of this quantity times t^{−s} at the points s = 1, s = 0, and s = χ_{k}. We will not explicitly exhibit the periodic term, so we stick to s = 1 and s = 0.

Using properties such as [15]

ζ(s, a) ∼ \frac{1}{s − 1} (s → 1), ζ(0, a) = \frac{1}{2} − a,

ζ(−1, a) = \frac{a^{2}}{2} − \frac{a}{2} − \frac{1}{12}, ζ′(0, a) = log Γ(a) − \frac{1}{2} log(2π)

and the functional equation of the Hurwitz’ ζ–function, an extremely boring computation gives the residue at s = 1 as \frac{9}{16t} and the residue at s = 0 as

\frac{1}{log 2}( − \frac{C}{2π} − \frac{1}{256π} (\sqrt{2} ζ(2, \frac{1}{8}) − 2 ζ(2, \frac{1}{4}) + \sqrt{2} ζ(2, \frac{3}{8}) − \sqrt{2} ζ(2, \frac{5}{8})

+ 2 ζ(2, \frac{3}{4}) − \sqrt{2} ζ(2, \frac{7}{8})) − \frac{3}{8} log π − log 2 + \frac{3}{8} log Γ(\frac{3}{8}) + \frac{3}{8} log Γ(\frac{5}{8})) .

(32)

Its numerical value is −1.287.

Now we bring the ‘forgotten factor’ \frac{4(1−u^{2})}{u} (see eq. (30)) again into the picture and have

T^{(2)}(z) ∼ (8t + O(t^{3})) · (\frac{9}{16t} − 1.287 + …)

∼ \frac{9}{2} − 10.298 t + …

∼ \frac{9}{2} − 10.298 · 2\sqrt{1 − 4z} + …

Hence, apart from the ubiquitous fluctuations,

\frac{[z^{n}] T^{(2)}(z)}{[z^{n}] B(z)} ∼ 10.298.  (33)

Thus, apart from fluctuations, the expected number of maximal subtrees 2 less than the register function of the entire tree is asymptotic to 10.298.

(With Maple, we get for instance the value \frac{[z^{30}] T^{(2)}(z)}{[z^{30}] B(z)} = 10.01241483.)

This must be put into perspective by the previous value 3.341, and the quotient

\frac{10.298}{3.341} = 3.082

is the asymptotic bifurcation ratio considered in this section (up to fluctuations, as always).

It is somehow surprising that we get a value 3.082 which is smaller then the previous values 3.341. However, the bifurcation ratio at the root is tending to 4, as was obtained in [16]. So we might be tempted to believe in a higher value. One should note for instance that all trees t with register function = 1 do not contribute at all to this “2–bifurcation rate”!

The considerations of this section can still be extended to higher bifurcation ratios. With an obvious notation, we have

T_{p}^{(d)}(z) = 2zT_{p−1}^{(d−1)}(z)\frac{R_{p−1}(z) + R_{p}(z)}{1 − 2z(B(z) − S_{p}(z))}.  (34)

It seems clear, that the explicit expressions for these quantities become quite unpleasant when d gets larger. The derivations presented in this paper should convince the reader however, that even in such a general case the asymptotic bifurcation ratio can be computed in principle.

5. Conclusion

We demonstrated that by the use of appropriate generating functions, Mellin transforms and singularity analysis problems which look very hard at first sight are reduced to more or less routine computations. The pattern is already described in the literature, and a forthcoming book of Flajolet and Sedgewick [8] will deal with it in much more detail.

It is somehow amusing that Catalan numbers and Catalan’s constant appear in the same problem! It is the first time that the present author has seen that.

Acknowledgment. The comments of one referee helped to improve this paper in many ways.

References

[1] M. Abramowitz, I. A. Stegun, Handbook of Mathematical Functions, Dover, New York (1970).

[2] N. G. de Bruijn, D. E. Knuth, S. O. Rice, The average height of planted plane trees, Graph Theory and Computing (R. C. Read, ed.), Academic Press, New York, (1972) pp. 15–22.

[3] L. Devroye, P. Kruszewski, A note on the Horton–Strahler number for random trees, Information Processing Letters 52 (1994), pp. 155–159. Reprinted in: Information Processing Letters 56 (1995), pp. 95–99.

[4] P. Flajolet, X. Gourdon, P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theor. Comput. Sci. 144 (1995), pp. 3–58.

[5] P. Flajolet, J.-C. Raoult, J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theor. Comput. Sci. 9 (1979), pp. 99–125.

[6] P. Flajolet and H. Prodinger, Register allocation for unary–binary trees, SIAM Journal on Computing 15 (1986), pp. 629–640.

[7] P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Disc. Math. 3 (1990) pp. 216–240.

[8] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Addison Wesley, in preparation (to appear (≥ 1996)).

[9] R. Kemp, The average number of registers to evaluate a binary tree optimally, Acta Informatica 11 (1979), pp. 363–372.

[10] A. Meir, J. W. Moon and J. A. Pounder, On the order of random channel networks, SIAM J. on Alg. Disc. Meth. 1 (1980) pp. 25–33.

[11] H. Prodinger, Die Bestimmung gewisser Parameter von binären Bäumen mit Hilfe analytischer Methoden, Lecture Notes in Mathematics 1114 (E. Hlawka, Ed.), Springer Verlag (1985) pp. 118–133.

[12] H. Prodinger, Some recent results on the register function of a binary tree, Proceedings of the Second Conference on Random Graphs, Posen 1985, Annals of Discrete Mathematics 33 (1987) pp. 241–260.

[13] H. Prodinger, Quelques techniques analytiques pour l’étude asymptotique des paramètres dans les arbres, (Lecture notes for the summer school in Ile de Ré 1983), English version in: EATCS Bulletin 47 (1992), 180–199.

[14] H. Prodinger, Solution of a problem of Yekutieli and Mandelbrot, In: Latin ’95 (R. Baeza-Yates, E. Goles, P.V. Poblete (Eds.), Lecture Notes in Computer Science 911 (1995) pp. 461–468.

[15] E. T. Whittaker, G. N. Watson, A course in modern analysis, Cambridge University Press (1930).

[16] I. Yekutieli and B. Mandelbrot, Horton–Strahler ordering of random binary trees, J. Phys. A: Math. Gen., 27 (1994) pp. 285–293.

Helmut Prodinger Department for Algebra and Discrete Mathematics TU Wien Wiedner Hauptstrasse 8–10/118 A-1040 Wien Austria email: proding@rsmb.tuwien.ac.at