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)