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

DOI10.1007/S00453-006-0122-8zbMATH Open1106.68087arXivcs/0509046OpenAlexW3101808853MaRDI QIDQ866964FDOQ866964

Authors: Gadiel Seroussi 

Publication date: 14 February 2007

Published in: Algorithmica (Search for Journal in Brave)

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

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

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
• scientific article; zbMATH DE number 3865302

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• On the path length of binary trees
• Staircase tilings and \(k\)-Catalan structures
• A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES

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)