Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home

Technical Reports


HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

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

Seroussi, Gadiel


Keyword(s): binary trees; t-ary trees; path length; universal types

Abstract: Please note: This abstract contains mathematical formula which cannot be represented here. We show that the number of t-ary trees with path length equal to p is where h(x)=-xlog2x-(1-x)log2(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. "Some of the most instructive applications of the mathematical theory of trees to the analysis of algorithms are connected with formulas for counting how many different trees there are of various kinds." D. E. Knuth, [7, p. 386].

10 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.