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

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

2005-09-15

arxiv.org/abs/cs/0509046v2

Algorithmica, Vol. 46, No. 3, pp. 557--565, 2006

Computer Science

Discrete Mathematics

July 2007: added journal reference and DOI, updated references, minor typographical corrections

Scientific paper

10.1007/s00453-006-0122-8

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$.

Affiliated with

Also associated with

No associations

Rating

On the number of t-ary trees with a given path length does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the number of t-ary trees with a given path length, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of t-ary trees with a given path length will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553018