Asymptotics of relaxed k-ary trees

A relaxed k-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree k. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed k-ary tree with n nodes for n → ∞. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term e^c n1/3 appears in all these cases. We also derive the recurrences for compacted k-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.