Digital search trees and basic hypergeometric functions
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.
I wrote a similar paper.
They use Heine's transformation for basic hypergeometric series instead of formulae of
Euler (corollaries of the q-binomial theorem).
helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)