On the Number of t-Ary Trees with a Given Path Length
G. Seroussi, G. Seroussi · 2004
We show that the number of t-ary trees with path length equal to p is h(t -1 ) tp log 2 p , where h(x)=-x log 2 x-(1-x) log 2 (1-x) is the binary entropy function. Besides its intrinsic combinatorial interest, the question recently arose in the context of information theory, where the number of t-ary trees with path length p estimates the number of universal types, or, equivalently, the number of di#erent possible Lempel-Ziv'78 dictionaries for sequences of length p over an alphabet of size t.