Application of basic hypergeometric series. (Q1421267)

The study of the average search costs in a digital search tree built from \(n\) random data relies on the explicit expression of the polynomial \(H_{n}(u)\), of degree \(n\) in \(u\), which has as the coefficient of \(u^{k}\) the expected number of nodes on this level. Using some results from the theory of \(q\)-hypergeometric functions the authors derive this explicit formula. Some background material from the theory of basic hypergeometric functions is also provided.