
Click here for full text:
On the number of tary trees with a given path length
Seroussi, Gadiel
HPL2004127
Keyword(s): binary trees; tary trees; path length; universal types
Abstract: Please note: This abstract contains mathematical formula which cannot be represented here. We show that the number of tary trees with path length equal to p is where h(x)=xlog_{2}x(1x)log_{2}(1x) is the binary entropy function. Besides its intrinsic combinatorial interest, the question recently arose in the context of information theory, where the number of tary trees with path length p estimates the number of universal types, or, equivalently, the number of different possible LempelZiv'78 dictionaries for sequences of length p over an alphabet of size t. "Some of the most instructive applications of the mathematical theory of trees to the analysis of algorithms are connected with formulas for counting how many different trees there are of various kinds." D. E. Knuth, [7, p. 386].
10 Pages
Back to Index
