pith. sign in

arxiv: cs/0509046 · v2 · submitted 2005-09-15 · 💻 cs.DM · cs.IT· math.IT

On the number of t-ary trees with a given path length

classification 💻 cs.DM cs.ITmath.IT
keywords numberlengthpathtreesentropyalphabetarosebesides
0
0 comments X
read the original abstract

We show that the number of $t$-ary trees with path length equal to $p$ is $\exp(h(t^{-1})t\log t \frac{p}{\log p}(1+o(1)))$, where $\entropy(x){=}{-}x\log x {-}(1{-}x)\log (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 different possible Lempel-Ziv'78 dictionaries for sequences of length $p$ over an alphabet of size $t$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.