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

DOI10.1007/S00453-006-0122-8MaRDI QIDQ866964zbMATH OpenOpenAlexFDO

Authors Gadiel Seroussi

Publication date 14 February 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0509046

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Information theory (general) (94A15)

Abstract: We show that the number of $t$-ary trees with path length equal to $p$ is $exp(h(t^{-1})tlogtfracplogp(1+o(1)))$, where $entropy(x)=-xlogx-(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$.

Recommendations

• scientific article; zbMATH DE number 1043915
• On the path length of binary trees
• scientific article; zbMATH DE number 4035870
• On the average path length of complete \(m\)-ary trees
• scientific article; zbMATH DE number 468836
• scientific article; zbMATH DE number 4041950
• scientific article; zbMATH DE number 4025461
• k-paths of k-trees
• scientific article; zbMATH DE number 4168708
• scientific article; zbMATH DE number 3865302

Cited in

(7)

• Staircase tilings and \(k\)-Catalan structures
• A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES
• ON THE ROUTING NUMBER OF COMPLETE d-ARY TREES
• Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
• On the path length of binary trees
• scientific article; zbMATH DE number 1043915 (Why is no real title available?)
• scientific article; zbMATH DE number 4168708 (Why is no real title available?)

This page was built for publication: On the number of \(t\)-ary trees with a given path length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866964)