DIGITAL SEARCH TREES AND BASIC

HYPERGEOMETRIC FUNCTIONS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. We use some concepts of basic hypergeometric series to give an extremely simple derivation of the exact formula for the expected number of nodes on level l in a random digital search tree, built from n random data.

1. Introduction

In this note we want to show that basic hypergeometric functions are the most natural concept when analyzing digital search trees. We do not give new formulæ but strikingly simple and elegant derivations for already existing ones.

In a previous paper [7], the present writer has already demonstrated the use of basic hypergeometric functions for approximate counting.

We only need a few things about hypergeometric functions and collect them in the next section.

2. Basics about basic hypergeometric functions

For the following we use [1]; compare also [2].

q–Pochhammer symbol.

(a)_{n} = (1 − a)(1 − aq) … (1 − aq^{n−1}),  (a)_{0} = 1,  (a)_{∞} = lim_{n→∞}(a)_{n}

We will only use this for q = \frac{1}{2}. Nevertheless we will stay with this classic notation. In many computer science texts the notation Q_{n} is used for (\frac{1}{2})_{n}.

Cauchy’s formula. (or: q–binomial theorem.)

∑_{n≥0} \frac{(a)_{n}t^{n}}{(q)_{n}} = \frac{(at)_{∞}}{(t)_{∞}} .

The special case a = 0 is generally attributed to Euler:

∑_{n≥0} \frac{t^{n}}{(q)_{n}} = \frac{1}{(t)_{∞}} .

Typeset by AMS-TEX

Now observe that

q^{\binom{n}{2}} = (−1)^{n}(0 − 1)(0 − q) … (0 − q^{n−1}) = (−1)^{n} lim_{ε→0} ε^{n}(1/ε)_{n}.

Hence

∑_{n≥0} \frac{q^{\binom{n}{2}}t^{n}}{(q)_{n}} = lim_{ε→0} ∑_{n≥0} \frac{(−εt)^{n}(\frac{1}{ε})_{n}}{(q)_{n}} = lim_{ε→0} \frac{(−t)_{∞}}{(−εt)_{∞}} = (−t)_{∞}.

This formula is also called Euler’s formula.

Heine’s transformation.

∑_{n≥0} \frac{(a)_{n}(b)_{n}t^{n}}{(q)_{n}(c)_{n}} = \frac{(b)_{∞}(at)_{∞}}{(c)_{∞}(t)_{∞}} ∑_{n≥0} \frac{(c/b)_{n}(t)_{n}b^{n}}{(q)_{n}(at)_{n}} .

Corollary.

∑_{n≥0}(y)_{n}z^{n} = (y)_{∞} ∑_{n≥0} \frac{y^{n}}{(q)_{n}(1 − zq^{n})}.

Proof. Set a = q, b = y, c = 0, and t = z in Heine’s formula. Then

∑_{n≥0}(y)_{n}z^{n} = \frac{(y)_{∞}(qz)_{∞}}{(z)_{∞}} ∑_{n≥0} \frac{(z)_{n}y^{n}}{(q)_{n}(qz)_{n}} .

Since \frac{(qz)_{∞}}{(z)_{∞}} = \frac{1}{1 − z} and \frac{(z)_{n}}{(qz)_{n}} = \frac{1 − z}{1 − zq^{n}}, the formula follows.

3. Level polynomials in digital search trees

A digital search tree in constructed like a binary search tree, but the decision to go down to the left or right is done according to the representation of the key as a binary string of bits. If the first bit is 0, the item goes to the left, otherwise to the right. Then the second bit is responsible for left or right, etc., until there is an empty node where the item can be stored.

The classic book [3] contains a more elaborate description.

Now, in order to study the average search costs in a digital search tree built from n random data (i.e., in every decision, 0 and 1 is equally likely), the polynomial H_{n}(u), which has as the coefficient of u^{k} the expected number of nodes on this level, is studied. By convention, the root is at level 0.

The formula

H_{n}(u) = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k−1}(u)_{k−1}, n ≥ 1, H_{0}(u) = 0,

appears already in Knuth’s book [3] (compare [4]). Remember, that we set q = \frac{1}{2}.

Louchard [5] gave explicit expressions for the coefficients of H_{n}(u); see also Mahmoud [6]. We write [u^{k}]H_{n}(u) for the coefficient of u^{k} in H_{n}(u), and similarly for generating functions in 2 variables.

Here we want to give the particularly simple derivation of this explicit formula by means of basic hypergeometric functions. It goes like this:

H(u, x) := ∑_{n≥1} H_{n}(u)x^{n} = ∑_{k≥1}(−1)^{k−1}(u)_{k−1} ∑_{n≥k} \binom{n}{k}x^{n}

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

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

Using the corollary of Heine’s transformation, we get

H(u, x) = \frac{x}{(1 − x)^{2}} (u)_{∞} ∑_{k≥0} \frac{u^{k}}{(q)_{k}(1 − \frac{x}{x−1}q^{k})}

= \frac{x}{1 − x}(u)_{∞} ∑_{k≥0} \frac{u^{k}}{(q)_{k}(1 − x(1 − q^{k}))}

= (u)_{∞} ∑_{k≥0} \frac{u^{k}}{(q)_{k}} q^{−k} [\frac{1}{1 − x} − \frac{1}{1 − x(1 − q^{k})}]

= \frac{(u)_{∞}}{1 − x} \frac{1}{(u/q)_{∞}} − (u)_{∞} ∑_{k≥0} \frac{(u/q)^{k}}{(q)_{k}} \frac{1}{1 − x(1 − q^{k})}.

In the last step we have used Cauchy’s (or Euler’s) formula. Since

\frac{(u)_{∞}}{(u/q)_{∞}} = \frac{1}{1 − u/q} ,

we can already read off the coefficient of x^{n}:

[x^{n}]H(u, x) = \frac{1}{1 − u/q} − (u)_{∞} ∑_{k≥0} \frac{(u/q)^{k}}{(q)_{k}} (1 − q^{k})^{n}.

Now we can also read off the coefficient of u^{l}:

[u^{l}x^{n}]H(u, x) = [u^{l}]H_{n}(u) = q^{−l} − ∑_{k=0}^{l} \frac{q^{−k}}{(q)_{k}} (1 − q^{k})^{n}[u^{l−k}](u)_{∞}

= q^{−l} − ∑_{k=0}^{l} \frac{q^{−k}}{(q)_{k}} (1 − q^{k})^{n} \frac{(−1)^{l−k}q^{\binom{l−k}{2}}}{(q)_{l−k}} .

In the last step we have used the second identity of Euler. This is (apart from trivial modifications) the formula (4) from [5].

The quantity

[u^{l}]\frac{1}{1 − u}H_{n}(u)

was also of interest in [5] (formula (6)). It is the coefficient of u^{l} in

\frac{1}{1 − u} \frac{1}{1 − u/q} − (qu)_{∞} ∑_{k≥0} \frac{(u/q)^{k}}{(q)_{k}} (1 − q^{k})^{n}.

Since

\frac{1}{1 − u} \frac{1}{1 − u/q} = \frac{1}{1 − q} \frac{1}{1 − u/q} − \frac{q}{1 − q} \frac{1}{1 − u},

we evaluate it to

\frac{1}{1 − q} (q^{n} − q) − ∑_{k=0}^{l} \frac{q^{−k}}{(q)_{k}} (1 − q^{k})^{n} \frac{q^{l−k}(−1)^{l−k}q^{\binom{l−k}{2}}}{(q)_{l−k}} .

In the same style we can also deal with another variety of polynomials, the so called leaf polynomials L_{n}(u). However, since L_{n}(u) = 1 − (1 − u/q)H_{n}(u) (see [3, 6]), the coefficients are obtained immediately from those for H_{n}(u).

References

1. G.E. Andrews, The Theory of Partitions, Addison Wesley, 1976.

2. G. Gasper and M. Rahman, Basic Hypergeometric Series, Cambridge Unversity Press, Cambridge, 1990.

3. D.E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973.

4. A. Konheim and D. Newman, A note on growing binary trees, Discrete Mathematics 4 (1973), 57–63.

5. G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Theoretical Informatics and Applications 21 (1987), 479–495.

6. H. Mahmoud, Evolution of Random Search Trees, John Wiley, 1992.

7. H. Prodinger, Approximate Counting via Euler Transform, Math. Slovaca 44 (1994), 569–574.

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@rsmb.tuwien.ac.at