Title: Asymptotic Enumeration of Compacted Binary Trees,
Abstract: A compacted tree is a graph created from a binary tree such that repeatedly
occurring subtrees in the original tree are represented by pointers to existing
ones, and hence every subtree is unique. Such representations form a special
class of directed acyclic graphs. We are interested in the asymptotic number of
compacted trees of given size, where the size of a compacted tree is given by
the number of its internal nodes. Due to its superexponential growth this
problem poses many difficulties. Therefore we restrict our investigations to
compacted trees of bounded right height, which is the maximal number of edges
going to the right on any path from the root to a leaf.
We solve the asymptotic counting problem for this class as well as a closely
related, further simplified class.
For this purpose, we develop a calculus on exponential generating functions
for compacted trees of bounded right height and for relaxed trees of bounded
right height, which differ from compacted trees by dropping the above described
uniqueness condition. This enables us to derive a recursively defined sequence
of differential equations for the exponential generating functions. The
coefficients can then be determined by performing a singularity analysis of the
solutions of these differential equations.
Our main results are the computation of the asymptotic numbers of relaxed as
well as compacted trees of bounded right height and given size, when the size
tends to infinity.