| author: | Charles Knessl and Wojciech Szpankowski |
|---|---|
| title: | Enumeration of Binary Trees and Universal Types |
| keywords: | Binary trees, types, Lempel-Ziv'78, path length |
| abstract: | Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them.
The number of such trees with n nodes is now known as the Catalan number.
Over the years various interesting questions about the statistics
of such trees were investigated (e.g., height and path length
distributions for a randomly selected tree). Binary
trees find an abundance of applications in computer science.
However, recently Seroussi posed a new and interesting problem motivated by
information theory considerations:
how many binary trees of a given path length (sum of depths) are there?
This question arose in the study of universal types of sequences.
Two sequences of length p have the same universal type
if they generate the same set of phrases in the incremental parsing
of the Lempel-Ziv'78 scheme since one proves that such sequences
converge to the same empirical distribution.
It turns out that the number of distinct types of sequences of length p
corresponds to the number of binary (unlabeled and ordered) trees, T ,
of given path length p p (and also the number of distinct
Lempel-Ziv'78 parsings of length p sequences).
We first show that the number of binary trees with given path length
p is asymptotically equal to
T . Then
we establish various limiting distributions for the number of nodes
(number of phrases in the Lempel-Ziv'78 scheme)
when a tree is selected randomly among all trees of given
path length p ~ 22p/(log 2 p)(1+O(log -2/3 p))p .
Throughout, we use methods of analytic algorithmics such as
generating functions and complex asymptotics, as well as
methods of applied mathematics such as the WKB method and matched
asymptotics. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Charles Knessl and Wojciech Szpankowski (2005), Enumeration of Binary Trees and Universal Types, Discrete Mathematics and Theoretical Computer Science 7, pp. 313-400 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm070117.ps.gz (375 K) |
| ps-source: | dm070117.ps (1140 K) |
| pdf-source: | dm070117.pdf (861 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.