On the number of t-ary trees with a given path length
| dc.creator | Seroussi, Gadiel | |
| dc.date | 2005-09-15 | |
| dc.date | 2007-07-15 | |
| dc.date.accessioned | 2026-07-07T08:17:52Z | |
| dc.date.available | 2026-07-07T08:17:52Z | |
| dc.description | 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$. | |
| dc.description | July 2007: added journal reference and DOI, updated references, minor typographical corrections | |
| dc.identifier | https://arxiv.org/abs/cs/0509046 | |
| dc.identifier | http://arxiv.org/abs/cs/0509046 | |
| dc.identifier | Algorithmica, Vol. 46, No. 3, pp. 557--565, 2006 | |
| dc.identifier | doi:10.1007/s00453-006-0122-8 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134239 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Information Theory | |
| dc.subject | G.2.1; G.2.2; E.4; H.1.1 | |
| dc.title | On the number of t-ary trees with a given path length | |
| dc.type | text |