  A compacted binary tree is a directed acyclic graph encoding a binary tree in
which common subtrees are factored and shared, such that they are represented
only once. We show that the number of compacted binary trees of size $n$ grows
asymptotically like $$\Theta\left( n! \, 4^n e^{3a_1n^{1/3}} n^{3/4} \right),$$
where $a_1\approx-2.338$ is the largest root of the Airy function. Our method
involves a new two parameter recurrence which yields an algorithm of quadratic
arithmetic complexity. We use empirical methods to estimate the values of all
terms defined by the recurrence, then we prove by induction that these
estimates are sufficiently accurate for large $n$ to determine the asymptotic
form. Our results also lead to new bounds on the number of minimal finite
automata recognizing a finite language on a binary alphabet. As a consequence,
these also exhibit a stretched exponential.
