Helmut Prodinger

Basic hypergeometric series, digital search trees, and approximate counting

It will be shown how the transformation formula of Heine from the theory of basic hypergeometric functions allows very simple and pleasant derivations of explicit forms of the level polynomials of digital search trees, as well as of explicit forms of the probabilities in the ``approximate counting'' problem. The latter problem also takes advantage of the Euler transform.