Résumé | When storing rooted trees it is useful to consider compression techniques. A simple idea is to store isomorphic subtrees only once and mark repeated occurrences with a pointer. A classical algorithm to establish such a compaction was analyzed by Flajolet, Sipala, and Steyaert. The resulting structure is called a compacted tree, being in fact no more a tree but a directed acyclic graph.
Our goal is the enumeration of such structures. Since the enumeration turns out to be extremely difficult, we restrict it to a sub problem by imposing a bound on the so-called right height. We solve this enumeration problem with the help of generating functions. Due to the superexponential growth of the counting sequence we use exponential generating function despite the fact that these objects are unlabeled. We first derive a calculus on exponential generating function capturing their recursive nature. This leads to a sequence of differential equations for the generating functions (also implying their D-finiteness) for which a singularity analysis is carried out.
This work is based on joint work with Antoine Genitrini, Bernhard Gittenberger, and Manuel Kauers. |