text:
\section{Introduction}
\label{sec:intro}

Most trees contain redundant information in form of repeated occurrences of the same subtree\footnote{In the rest of the paper,
a subtree of a given tree contains a root and all descendants of the original tree. Such a substructure
is sometimes called a fringe subtree.}.
In order to get an efficient representation in memory,
these trees can be compacted by representing each occurrence only once.
The removed subtrees
are replaced by pointers which link to the shared subtree.
Such structures are classically named as \emph{directed acyclic graphs} or short as \emph{DAGs}.

Flajolet \emph{et al.}, in their extended abstract~\cite{flss90}, analyzed in detail the gain in memory
of the compaction. Some proofs have been omitted and have not been stated later.
This gap was closed in~\cite{bousquet2015xml}, where the framework was extended to other DAG structures
and analyzed in the context of XML compression.
Furthermore, Ralaivaosaona and Wagner extended in \cite{RalaivaosaonaWagner2015Repeated} the analysis of the gained memory to simply generated families of trees.

The latter two papers on the quantitative analysis of the compaction process,
studied the transformation of a given set of trees of given size
to the set of compacted trees in order to determine the average rate of compaction.
We focus on a different aspect, namely the enumeration problem of compacted binary trees.
On the one hand, enumerating combinatorial structures is important if one wants to understand shape characteristics
of large random structures or for uniform random generation of those structures. On the other
hand, the enumeration of particular classes of DAGs is in general a difficult problem which
requires the extension of combinatorial methodology and is therefore interesting in its own right.

One of the difficulties in the enumeration of compacted binary trees lies in the fact that a
compacted binary tree of size $n$ could arise from a binary tree whose size belongs to the whole interval $n,\dots, 2^n$. Thus, a brute-force approach is hopeless.

The first papers about the enumeration of DAGs appeared in the 70's. Robinson
presented two distinct approaches~\cite{Robinson70, Robinson77}
based either on some inclusion-exclusion method or on P\'olya's enumeration theory~\cite{Polya37}.
Combining combinatorial arguments and analytic methods the asymptotic number of labeled DAGs was
determined in \cite{BRRW86}, for connected structures then in \cite{BR88}.
The first investigation of shape
parameters seems to go back to McKay \cite{McKay89}. Recently, enumeration results for many
particular classes of DAGs can be found in the literature, see for instance \cite{BGG11, BGGG17,
BGGJ13, GS05, liskovets2006exact, MSW15, St03, St04, Wa13}, as well as investigations on the (random) generation of particular DAGs, see \cite{ADK05, CD12, MDB01, MP04}.

A now classical way for enumeration is the use of generating functions.
In this context, precisely for labeled structures (see paper~\cite{robinson1973dags}),
Robinson designed generating functions of a very particular nature to solve an asymptotic
counting problem concerning DAGs. The classical types of generating functions like ordinary and
exponential ones were not suited to the problem.

We are facing the same problem in the enumeration of compacted trees. Indeed, due to the fact that
compacted trees are unlabeled combinatorial structures, which are moreover closely related to
plane trees, a treatment with ordinary generating functions will be the first choice. However, the
fast growth of the counting sequence requires the use of exponential generating functions. In
order to be able to get asymptotic results, we will confine ourselves to certain subclasses of the
class of compacted trees as well as some related classes by relaxing certain conditions. Moreover,
we will develop a calculus for exponential generating functions designed for these classes.
Bounding the right height of our DAGs leads to a sequence of D-finite functions (see
\cite{KauersPaule11,stan99} for introductions to the subject) for which it is
possible to analyze their differential equations and obtain finally our main result. Likewise,
in other enumeration problems for particular classes of DAGs bounding a certain parameter turned
intractable recurrences into D-finite ones. Examples are the enumeration of certain classes of
lambda-terms \cite{BGG11, BGGJ13, BGGG17} or increasing series-parallel DAGs \cite{BDGP17}.

\subsubsection*{Plan of the paper}

Our combinatorial structures are based on the fundamental properties of the compaction procedure.
We will first analyze some properties of this classical procedure (linked to the \emph{common
subexpression problem}) in Section~\ref{sec:creating}.

Then we will define the basic concepts and state our main results in Section~\ref{sec:mainres},
see Theorems~\ref{theo:relaxededmain} and \ref{theo:compactedmain}.

Some basic observations concerning the structure of compacted trees will then be presented in
Section~\ref{sec:struct}.

These will help us to state a combinatorial and (most importantly) recursive specification
of the problem in Section~\ref{sec:recurrence}. A further important result is the derivation of
\emph{a recurrence relation for the number of compacted binary trees}, see Theorem~\ref{theo:comprecursion}.
This recurrence is not classical at all, and we are not able to solve it explicitly.

Due to this fact, we follow yet a different approach in the remaining part of this work:
We will use exponential generating functions to model our problem, as the superexponential growth
rate of the counting sequence suggests, though we are dealing with
unlabeled combinatorial structures. Therefore, a new calculus translating certain set operations for
classes of compacted trees into algebraic operations of exponential generating functions will be
developed in Section~\ref{sec:operations}.

Section~\ref{sec:relaxed} is devoted to a simplified problem, the study of the counting problem of
\emph{relaxed binary trees}. These DAGs are in a sense compacted trees where the restriction of
uniqueness on the subtrees is relaxed. In particular, compacted trees are a subset of relaxed
binary trees. With the same methods as used on compacted trees we are able to derive a recurrence
relation. However, this recurrence relation is as difficult as the first one for compacted trees.

A natural constraint for compacted trees seems to bound some specific depth limit, the so-called
right height. This is the maximal number of edges directed to the right which appear on any path
from the root to a leaf. In Section~\ref{sec:relaxed}, the calculus developed in
Section~\ref{sec:operations} enables us to derive a differential equation for the generating
function of relaxed trees for each bound $k$ on the right height. This sequence of D-finite
differential equations follows a rather explicit recursive scheme, presented in
Theorem~\ref{theo:Dkprop} which allows us to analyze the dominant singularities of the solutions
of the differential equation for any $k$. Eventually, this strategy is successful and we are able to
determine the asymptotic number of relaxed binary trees of bounded right height.

Finally, in Section~\ref{sec:compacted} we modify the results of the previous section to cover the
case of compacted trees as well. Again, we derive a sequence of D-finite differential equations where, as in
Section~\ref{sec:relaxed}, the dominant singularities of the generating function are regular
singularities of the differential equation. This allows us to extract the asymptotic behavior
of the counting sequence, which contains irrational powers of $n$. The necessary information is
directly extracted from the differential equations. Except for a few exceptions, they do not have
closed form solutions.

\section{Creating a compacted tree}
\label{sec:creating}

Many problems in computer science and computer algebra involve redundant information.
A strategy to save memory is to store every instance only once and to point to already existing
instances, whenever an instance appears repeatedly.
In \cite[Proposition 1]{flss90} a compression algorithm was presented, and it was shown that for a given tree of size $n$, its compacted form can be computed in expected time $\mathcal{O}(n)$.
However, such procedures have been known since the $1970$'s (see~\cite{flss90,DowneySethiTarjan1980variations} and especially the ``value-number method'' in compiling~\cite[Section~6.1.2]{aho1986compilers}).
Figure \ref{fig:procUID} shows this procedure, which follows a top-down decomposition scheme
(i.e.~post-order traversal) of labeled binary trees.
Every node (or actually the subtree whose root is the respective node)
is associated with a ``unique identifier'' (\emph{uid}).
Two subtrees are equivalent if and only if the uid's are the same.

\begin{figure}[ht]
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}\\[-0.8\baselineskip]
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}
\texttt{function UID(T : tree) : integer;}\\[-0.5\baselineskip]
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}%
\vspace{-0.5\baselineskip}
\begin{verbatim}
global counter : integer, Table : list;
begin
   if  T  =  nil
      then  return(O);
      else
         triple  :=  <root(T),UID(left(T)),UID(right(T))>;
         if  Found(triple,Table)
            then  return(value_found);
            else  counter  :=  counter+l;
               Insert  pair  (triple,counter)  in  Table;
               return(counter);
         fi
   fi
end
\end{verbatim}
\vspace{-1\baselineskip}
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}\\[-0.8\baselineskip]
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}
\caption{\small The \texttt{UID} procedure from \cite[Fig.~2]{flss90} which computes
``unique identifiers'' for all (fringe) subtrees of a given binary tree $T$.
It is assumed that \texttt{counter} is initially set to $0$.
Table is a global list that maintains associations between triples and already
computed \texttt{UID}'s; it is also initially empty.
The function \texttt{root(T)} extracts the label of the root of tree $T$. }%
\label{fig:procUID}%
\end{figure}

We now give an example of the behavior of the procedure for an arithmetic expression.

\begin{example}
 Consider the labeled tree necessary to store the arithmetic expression
 \texttt{(* (- (* x x) (* y y)) (+ (* x x) (* y y)))} which represents
 $(x^2-y^2)(x^2+y^2)$. The ``Table'', built by the \texttt{UID} procedure, contains
	\begin{align*}
		((x,0,0), 1),   && ((*,1,1), 3),   && ((-,3,4), 5),   && ((*,5,6), 7), \\
		((y,0,0), 2),   && ((*,2,2), 4),   && ((+,3,4), 6),
	\end{align*}
	and the tree in its full and compacted version is shown in Figure \ref{fig:UIDex}.
\end{example}

\begin{figure}[ht]%
	\begin{center}
	\includegraphics[width=0.9\textwidth]{arithmeticexpression}%
	\caption{\small Tree and compacted tree associated with
	\texttt{(* (- (* x x) (* y y)) (+ (* x x) (* y y)))} computed by the
	\texttt{UID} procedure from Figure \ref{fig:procUID}.}%
	\label{fig:UIDex}%
	\end{center}
\end{figure}

Motivated by this procedure, based on a post-order traversal of the tree,
we define an ad hoc DAG-structure, which we call a \emph{compacted binary tree},
that encodes the result of the compaction of the tree.
The trees under consideration are \emph{full binary} in the sense that their
nodes have either 0 or 2 children.
Furthermore, in the definition we refer to subtrees: a \emph{fringe subtree} or short \emph{subtree}
is the tree which corresponds to a node and all its descendants.
In this paper we only consider such subtrees.

\begin{definition}
	\label{def:compactedbinarytree}
	A \emph{compacted binary tree} is a DAG computed by the \texttt{UID}
	procedure from a given full binary tree.
	Every edge leading to a subtree that has already been seen
	during the traversal is replaced by a new kind of edge, a \emph{pointer},
	to the already existing subtree. The \emph{size} of the compacted
	binary tree is defined by the number of its internal nodes.
\end{definition}

In the sequel we will only consider full binary trees and their compacted forms.
Thus, the term \emph{compacted trees} means compacted binary trees.
In Figure~\ref{fig:compacted_trees_n123}, we represent all compacted trees of size $0,1$ and $2$.

\begin{figure}[ht]
	\centering
	\includegraphics[width=0.7\textwidth]{comptrees012}%
	\caption{\small All compacted trees of size $n=0,1,2$. The labels in the nodes are the uids of
the corresponding subtrees. But note: The labels are not belonging to the combinatorial objects.
Compacted trees are unlableled graphs.}
	\label{fig:compacted_trees_n123}
\end{figure}

The subclass of DAGs we are interested in is strongly influenced by properties of trees.
In particular, compacted trees are connected and plane. The out-degree\footnote{For the terms out-
and in-degree, source, sink, and so on, we interpret an undirected edge as directed away from the
root, in accordance with a node-child relation.} of each vertex is equal to $2$,
except for the unique sink (leaf) for which it is $0$.
Furthermore, there is a unique source, which is the root.

The latter properties are induced by the full binary tree structure.
Next, we treat the specific properties of the \texttt{UID} procedure.
The result of the algorithm strongly depends on the chosen traversal.
In this case the post-order traversal is used --
but one could also consider a different one.
There are two important observations.
First of all, it has an important consequence on the pointers:
\begin{prop}
\label{prop:pointerrestriction}
In a compacted tree the pointers only point to previously discovered trees.
\end{prop}

In other words, the ordering imposed by the traversal restricts the possible choices of the pointers.

\begin{definition}
	For any compacted tree of size $n$, the \emph{spine} is the structure (with $n$ nodes)
	obtained from the compacted tree by deleting all pointers and the leaf.
\end{definition}
In the Figure~\ref{fig:spine}, from left to right, we see a compacted tree (without details on the pointers) and its spine. Furthermore, every distinct subtree is stored only once.
In terms of the corresponding compacted trees this translates into
uniqueness of every subtree.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.2\textwidth]{cp_tree_new}
	\qquad \qquad \qquad
	\includegraphics[width=0.2\textwidth]{spine_cp_tree_new}
	\caption{\small A compacted tree and its spine.}
	\label{fig:spine}
\end{figure}

\section{Main results}
\label{sec:mainres}

Before being able to state our main results we have to define further combinatorial classes.
Indeed, the uniqueness condition for compacted trees caused some difficulties in their
enumeration. So, we will first analyze a simpler class where we drop this condition.

\begin{definition}
A \emph{relaxed compacted binary tree} (short \emph{relaxed binary tree}, or just \emph{relaxed
tree}), of size $n$ is a directed acyclic graph consisting
of a binary tree with $n$ internal nodes, one leaf, and $n$ pointers.
It is constructed from a binary tree of size $n$, where the first leaf
in a post-order traversal is kept and all other leaves are replaced by pointers.
These links may point to any node that has already been visited by the post-order traversal.

Obviously, the notion of spine adapts to the class of relaxed trees.
\end{definition}

In fact, let us give another way to interpret compacted trees:
compacted trees are relaxed trees with the restriction that all subtrees
in the spine are unique.
Note that this condition does not hold for all relaxed trees. In particular compare Figure~\ref{fig:relaxed_tree_3} for the smallest relaxed tree which is not a compacted tree.

\begin{figure}[ht]
	\centering
	\includegraphics[width=0.55\textwidth]{relaxednotcompacted}
	\caption{\small Left: the smallest relaxed tree that is not a compacted tree; right: the corresponding unique compacted tree.}
	\label{fig:relaxed_tree_3}
\end{figure}

The asymptotic enumeration of relaxed trees is still too complicated. We will derive recurrence
relations for their counting sequence as well as for the counting sequence of compacted trees. In
order to obtain asymptotic results, we restrict the right height.

\begin{definition}
For any relaxed tree, we define its \emph{right height} to be the maximal number of right edges
on any path from the root to another node in the spine (of the relaxed or compacted tree under
consideration).
The \emph{level} of a node is the number of right edges on the path from the root to this node.
\end{definition}

Figure~\ref{fig:rightheight} introduces an example and a natural way of representing a relaxed tree
in order to emphasize these notions. It proves convenient to rotate the trees by $45$ degrees.
\begin{figure}[htb]
	\centering
	\includegraphics[width=0.2\textwidth]{rheight1}
	\qquad \qquad \qquad
	\includegraphics[width=0.26\textwidth]{rheight2}
	\caption{\small A compacted tree with right height~$2$.
	Nodes of level~$0$ are colored in red, nodes of level~$1$ in blue,
	and the node of level~$2$ in green. }
	\label{fig:rightheight}
\end{figure}

Bounding the right height defines a sequence of classes which follows a recursive construction
principle. We will eventually exploit this structure and obtain our main results,
the asymptotic number of relaxed trees with $n$ internal vertices and the analogous result for
compacted trees.

\begin{theo}[Asymptotics of relaxed trees with bounded right height]
	\label{theo:relaxededmain}
	The number $r_{k,n}$ of relaxed trees with right height at most $k$ is for $n \to \infty$ asymptotically
	equivalent to
	\begin{align*}
		r_{k,n} \sim \gamma_k  n! \left(4 \cos\left(\frac{\pi}{k+3}\right)\right)^{n}  n^{-k/2},
	\end{align*}
	where $\gamma_k \in {\mathbb R}$ is independent of $n$.
\end{theo}

\begin{theo}[Asymptotics of compacted trees with bounded right height]
	\label{theo:compactedmain}
	The number $c_{k,n}$ of compacted trees with right height at most $k$ is for $n \to \infty$ asymptotically equivalent to
	\begin{align*}
		c_{k,n} \sim \kappa_k   n!
		\left(4 \cos\left(\frac{\pi}{k+3}\right)\right)^{n}
		n^{- \frac{k}{2} - \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\frac{1}{\cos^2\left(\frac{\pi}{k+3} \right)}}

						,
	\end{align*}
	where $\kappa_k \in {\mathbb R}$ is independent of $n$.
\end{theo}

Therefore, we can also answer the question (at least asymptotically) of how many relaxed trees are actually compacted trees.
Combining Theorems~\ref{theo:relaxededmain} and \ref{theo:compactedmain} we get the following result.

\begin{coro}[Proportion of compacted among relaxed trees]
	\label{coro:compamongrelaxed}
	Let $c_{k,n}$ ($r_{k,n}$) be the number of compacted (relaxed) binary trees with right height at most $k$. Then, for $n \to \infty$ we have
	\begin{align*}
		\frac{c_{k,n}}{r_{k,n}} \sim
			\frac{\kappa_k}{\gamma_k} n^{- \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\frac{1}{\cos^2\left(\frac{\pi}{k+3} \right)}}
			= o\left(n^{-1/4} \right)
			.
	\end{align*}
\end{coro}

Thus, the number of compacted trees among relaxed trees for large $n$ is negligible. This result quantifies the restriction of uniqueness of subtrees in compacted trees.

\section{On the structure of compacted trees}
\label{sec:struct}

In this section we will discuss some basic observations concerning the structure of compacted
trees. First note that pointers may point to vertices lying outside the subtree of the pointer's
start node (compare with Figure~\ref{fig:UIDex} and \ref{fig:compacted_trees_n123}). Such subtrees of compacted trees
cannot be compacted trees themselves. For this reason, we define the concept of \emph{c-subtrees}.

\begin{definition}
	 A \emph{c-subtree} is a subtree of a compacted tree.
	 A \emph{cherry} is a c-subtree where both children of the root are pointers.
\end{definition}
A cherry is, in a sense, the ``minimal'' construction to create a new subtree.
It consists of a node and two pointers, which point to already existing c-subtrees.
An example is given in Figure~\ref{fig:compacted_trees_n123}: In the rightmost tree, the $c$-subtree
with the root node labeled by $2$ is a cherry. Such a cherry is also not a compacted tree in the sense
of Definition~\ref{def:compactedbinarytree} as the root node has two pointers which point to
an external structure.
The only compacted tree of size $1$ is also given in the same Figure.

With this terminology we are able to analyze some aspects of the DAG-structure of compacted trees.
First, we look at the spine.

\begin{lemma}
	\label{lem:deletepointers}
	The spine of a compacted tree of size $n$ is a binary tree of size $n$.
\end{lemma}

\begin{proof}
	Obviously, by deleting the leaf and the pointers we get a rooted, acyclic graph.
	It remains to show that this graph is connected.
	Assume that there exists a pointer which is the only connection between two parts of the compacted tree.
	By the \texttt{UID} procedure a pointer corresponds to a multiple occurrence of a subtree.
	Therefore we get a contradiction, as this subtree must already exist in the tree and is,
	therefore, connected with the root via internal edges.
\end{proof}

Let us remark that the tree structure of a spine is binary in the sense that its nodes are either of out-degree $2$,
 $1$ (with two possibilities, either with a left child or with a right child), or $0$.

\begin{prop}
	\label{prop:characterizingcompactedtrees}
	From any binary tree of size $n$, we can build a compacted tree of size $n$, with the following operations:
	\begin{enumerate}
		\item Add a leaf as left child of the leftmost node of the binary tree.
		\item Add pointers to every node such that every node except the leaf has out-degree $2$.
		\item\label{item:cherryuniqueness} Let the pointers point to internal nodes which are in post-order traversal
			before the root node (under consideration) such that the corresponding subtree is unique (not already existing).
	\end{enumerate}
	Every compacted tree of size $n$ can be constructed this way.
\end{prop}

\begin{proof}
	A simple way to build a compacted tree by using the spine is the following one.
	Add the leaf to the leftmost node of the binary tree. Then traverse the binary tree
	by using the post-order traversal, and each time one meets a node with out-degree less than $2$
	we add $1$ or $2$ pointers to the last node one visited (this ensures uniqueness of the new subtree).

The last statement is obvious, since every compacted tree can be reconstructed from its spine
using only the operations listed above. By Lemma~\ref{lem:deletepointers} the spine has the same
size as the compacted tree.

\end{proof}

Note that in the previous proposition the compacted tree does not need to be the result of the compaction
of the initial binary tree under consideration (even if it is a full binary tree).
Furthermore, in many cases we can construct several compacted trees by enriching the same binary tree.
So the function mapping compacted trees to its spine is not one-to-one.

The last result also tells us that cherries are the fundamental structures that guarantee the uniqueness
of c-subtrees.
Indeed, if a cherry violates the condition implicit in the third operation listed in Proposition~\ref{prop:characterizingcompactedtrees},
 the structure is not a compacted tree according to our definition, but only
a relaxed tree.

A different explanation why cherries are the crucial objects for uniqueness
comes from the property that the compaction procedure generates an increasing set of elements,
i.e.~already seen subtrees.
Here we mean that the next element is constructed by a new internal node and previous,
already built, elements.
In particular, the first element is always a leaf, the second one is always
an internal node with two leaves as children (a ``classical cherry'').
Then, as a third element one has an element with a new internal node and a cherry as its left
child, or as its right child, or on both sides. How will further elements be built
such that the uniqueness property is maintained? Let us focus on the bad ways to do so, i.e. we
ask: What is forbidden?
There are two cases according to the type of the current node (in the post-order traversal of the
tree):

\begin{itemize}
	\item The current node is a cherry: The only forbidden way to place the two pointers is by
choosing an already generated subtree and letting the two pointers of the cherry point to the
children of the subtree. Note that the children of an already generated subtree must have been
generated before. Thus, for any already generated subtree there is one forbidden configuration for
the placement of the pointers.
	\item The current node is not a cherry: In this case at least one edge is not a pointer.
		But then it can easily be seen by induction that the subtree of the corresponding
child is unique. Hence, there is no restriction on placing the pointer since the current node
will always generate an new subtree.
\end{itemize}

This idea will be picked up in the next section and used to derive a recurrence relation for the
number of compacted trees of size $n$. Besides, it shows that we have to be careful only when
dealing with nodes having two pointers (see Section~\ref{sec:compacted}).

\section{Counting compacted structures by recurrence}
\label{sec:recurrence}

Using the properties stated in the last section for compacted trees, we are now
able to exhibit a combinatorial recurrence based on a decomposition of
the structures under consideration.

\subsection{A recurrence relation for compacted trees}

Let $c_n$ be the number of compacted binary trees of size $n$.
Recall that Figure~\ref{fig:compacted_trees_n123} showed all compacted trees
of size $0,1$ and $2$. It is easily checked that the first few terms of the sequence are given by
\begin{align*}
	\left( c_n \right)_{n \geq 0} &=
		\left(
			1, 1, 3, 15, 111, 1119, 14487, 230943, 4395855, 97608831,
		\ldots \right).
\end{align*}
Note that this sequence is not found in Sloane's Online Encyclopedia of Integer Sequences.
As a first step we derive a recursion representing this sequence.

Suppose that we perform a post-order traversal on a tree and that already $p$ c-subtrees have been
discovered. Then the current node is the root of another c-subtree.
Let $\Gamma_{n,p}$ denote the class of all c-subtrees
of size $n$ that may show up as such a c-subtree. Then we may think of the already
compacted subtrees as an external pool of trees where our pointers can point to additionally when
continuing our traversal. For an illustration see Figure~\ref{fig:pool}.
Note that the leaf is always part of this pool but not counted,
and all subtrees in the pool must be constructed out of elements from the pool.
In this sense the pool is closed in itself, and its evolution in the compaction procedure is an increasing sequence of sets.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.32\textwidth]{poolconstruction} \qquad \qquad \qquad \qquad
	\includegraphics[width=0.3\textwidth]{poolconstruction2}
	\caption{\small The two cases of the pool construction of Theorem~\ref{theo:comprecursion}. The pool (circled elements) represents the already visited c-subtrees the pointers may point to. In the second case it may also point to the c-subtrees of the left sibling.}
	\label{fig:pool}
\end{figure}

We define the size of the pool to be the number of distinct subtrees
with at least one internal node.
Thus, the pool for the trees in $\Gamma_{n,p}$ has size $p$ and consists of $p+1$ distinct
c-subtrees. This artificially looking convention will simplify the later analysis.

\begin{theo}
	\label{theo:comprecursion}
	Let $n,p \in \mathbb{N}$, and $\Gamma_{n,p}$ as above. Moreover, we denote the cardinality of
$\Gamma_{n,p}$ by $\gamma_{n,p}$. Then
	\begin{align}
		\gamma_{n+1,p} &= \sum_{i=0}^{n} \gamma_{i,p} \; \gamma_{n-i,p+i}, \qquad \text{ for } n \geq 1, \label{eq:recCnp}\\
		\gamma_{0,p} &= p+1, \label{eq:recCnpI1}\\
		\gamma_{1,p} &= p^2 + p + 1. \label{eq:recCnpI2}
	\end{align}
\end{theo}

\begin{proof}
An element of $\Gamma_{n,p}$ consists of $n$ internal nodes connected by $n-1$ internal edges. The remaining $n+1$ edges of the compacted binary tree are pointers (the possible edge to the leaf may be interpreted as a pointer). These must be chosen in such a way that no subtree is generated twice. Additionally, they may point either to a c-subtree of the pool or to a c-subtree of its left sibling, see Figure~\ref{fig:pool}. The second condition is due to the post-order traversal of the tree by the \texttt{UID} procedure.

	Now we can give a recursive decomposition of such trees. Let $t$ be a c-subtree with $n+1$
nodes and a pool of size $p$. The root of $t$ has a left and a right subtree attached to $i$ and
$n-i$, (for $i=0,\ldots,n$) internal nodes, respectively. Note that every internal node also
represents a c-subtree. For the left child the pool remains the same as for its parent. However,
for the right child the pointers may additionally point to c-subtrees of its left sibling. Hence,
the pool is increased by the size of its left sibling. These considerations directly give Equation~\eqref{eq:recCnp}.

	Next, let us consider the initial conditions \eqref{eq:recCnpI1} and \eqref{eq:recCnpI2}. The c-subtrees with no internal nodes can be interpreted as pointers. These may point to any element of the pool, hence $\gamma_{0,p} = p+1$.

	The c-subtrees with $1$ internal node are cherries, whose both children are not internal nodes. Hence, they consist either of two pointers or of a leaf and a pointer. As the pool always contains a leaf, it is sufficient to consider the first case. Then these two pointers have $p+1$ possibilities each to point at. Among these $(p+1)^2$ cases are $p$ which must be excluded as they are the ones already found in the pool. Note that these can be recreated by letting the pointers point to the same children as the ones found in the pool. Hence, we get
	\begin{align*}
		\gamma_{1,p} &= (p+1)^2-p = p^2+p+1. \qedhere
	\end{align*}
\end{proof}

\begin{coro}
The number $c_n$ of compacted trees of size $n$ is equal to $\gamma_{n,0}$.
\end{coro}
Obviously, by Theorem~\ref{theo:comprecursion} the numbers $\gamma_{n,0}$ depend on the numbers $\gamma_{k,p}$
for all $0 \leq k \leq n$ and all $0 \leq p \leq n$. Thus their computation is quadratic in time and memory.

\begin{lemma}
\label{lem:compgrowth}
The number of compacted binary trees of size $n$ satisfies the following bounds:
\[
n! \leq c_n \leq \frac{1}{n+1} \binom{2n}{n} \; n!.
\]
\label{lem:upper_bound}
\end{lemma}

\begin{proof}
Let us first consider the lower bound:
Consider the subclass of chains. These are trees where the left child is always an internal edge and the right child is a pointer, see Figure~\ref{fig:R0}. Let $a_n$ be the number of chains with $n$ internal nodes. The leaf is the only such object of size~$0$. Hence, we have $a_0=1$. A chain of size $n+1$ can be constructed from a chain of size $n$ by appending a new root node with a pointer. The pointer has $n+1$ possible locations to point to. This implies, $a_{n+1} = (n+1) a_n$. We get the lower bound $a_n = n!$.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.6\textwidth]{R0}
	\caption{\small The number of compacted trees of size $n$ of right height at most $0$ is equal to $n!$.}
	\label{fig:R0}
\end{figure}

Let us now focus briefly on the upper bound: Consider all possible spines. There are $\text{Cat}_n = \frac{1}{n+1}\binom{2n}{n}$ (Catalan numbers) such structures, as they are binary trees.
Next, note that a binary tree of size $k$ has $k+1$ leaves. In our case these are pointers. By Proposition~\ref{prop:pointerrestriction} pointers can only point to previously discovered trees. Hence, every pointer has at most $k$ possibilities to point at. This proves the upper bound.
\end{proof}

The last result implies that the asymptotic growth of compacted trees satisfies
$
	c_n = \mathcal{O}(n! \; 4^n \; n^{-3/2}),
$
but it is also bounded from below by $n!$.
Thus, an ordinary generating function for $(c_n)_{n\in\mathbb N}$ would have radius of
convergence equal to zero.
Hence, we will need to use exponential generating functions in order to ensure a non-zero radius of
convergence.
This idea will be used in the next sections. But first, let us state a simplified problem,
which also proves very difficult to solve, but is not as technical.

\subsection{A recurrence relation for relaxed compacted trees}
\label{sec:relaxedproblemdef}

Let $r_n$ be the number of relaxed trees of size $n$. The first few terms of the sequence are given by
\begin{align*}
	\left( r_n \right)_{n \geq 0} &=
		\left(
			1, 1, 3, 16, 127, 1363, 18628, 311250, 6173791, 142190703,
		\ldots \right).
\end{align*}
This sequence is given by the sequence A$082161$ in the OEIS.
The latter counts the number of deterministic completely defined initially connected
acyclic automata with $2$ inputs and $n$ transient unlabeled states
and a unique absorbing state, see~\cite{liskovets2006exact}.
The bijection of these structures to our (enriched) trees is obvious,
by traversing relaxed trees from the root to the leaf.
Remark that the asymptotic behavior of the number of such structures seems not to be known.

Let $\delta_{	n,p}$ be the number of relaxed c-subtrees of size $n$ and a pool of size $p$.
We directly get a recurrence relation for these numbers, that is directly linked
to the one for $(\gamma_{n,p})_{n,p \in \mathbb{N}}$:
\begin{coro}
	\label{coro:relaxedrecurrence}
	Let $n,p \in \mathbb{N}$, then
	\begin{align}
		\delta_{n+1,p} &= \sum_{i=0}^{n} \delta_{i,p} \; \delta_{n-i,p+i}, \qquad \text{ for } n \geq 1, \label{eq:recRnp}\\
		\delta_{0,p} &= p+1. \label{eq:recRnpI1}
	\end{align}
	The number of relaxed trees of size $n$ is equal to $\delta_{n,0}$.
\end{coro}
\begin{proof}
	This is a direct consequence of Theorem~\ref{theo:comprecursion} and the fact that we dropped the uniqueness restriction enforced by \eqref{eq:recCnpI2}.
\end{proof}

Note that the nature of the recurrence relation did not change compared to the one of the compacted case.
Unfortunately, we were not able to find an explicit solution, or to continue from here.
A more promising approach is the one of generating functions introduced in the next section.

\section{Operations on trees}
\label{sec:operations}

We have seen in the previous sections that the numbers $c_n$ and $r_n$ are growing like $n!A^n$, (compare Lemma~\ref{lem:compgrowth}, which also holds in the relaxed case).
Therefore we introduce exponential generating functions in order to get a non-zero radius of convergence.
But then there arises a problem in the construction: exponential generating functions are designed
for labeled objects, but we are dealing with unlabeled ones. Thus, we first investigate how the nature
of exponential generating functions reflects the construction of such enriched trees.

The use of non-standard generating functions in the enumeration of DAGs is not new.
Robinson~\cite{robinson1973dags} introduced the so-called ``special generating function''
\begin{align*}
	A(t) &= \sum_{n \geq 0} a_n 2^{-\binom{n}{2}} \frac{t^n}{n!}
\end{align*}
to derive nice expressions of such generating functions for labeled DAGs.
This \emph{ad hoc} generating function seems not applicable in our context,
but exponential generating functions are.

For this purpose, we restrict ourselves to a subclass: relaxed trees of bounded right height, and
we are going to derive their exponential generating functions.
In this context we introduce the following notations: Let $\mathcal{R}$ be a combinatorial class.
Its exponential generating function is given by $R(z) = \sum_{n \geq 0} r_n \frac{z^n}{n!}$
where $r_n$ denotes the number of elements in $\mathcal{R}$ of size $n$.

\begin{lemma}(Adding a new root)
	\label{lem:approot}
	Let $\mathcal{R}$ be a combinatorial subclass of relaxed trees, and let $\mathcal{S}$
	be the combinatorial class whose elements consist of a new root node, with an element of $\mathcal{R}$
	as its left child, and with a pointer as its right child.
	Then,
	\begin{align*}
		S(z) = zR(z).
	\end{align*}
\end{lemma}

\begin{proof}
	Consider a relaxed tree of $\mathcal{R}$ of size $n$.
	Adding a new root node with the considered tree as its left child creates a tree of size $n+1$.
	The new pointer has $n+1$ possibilities, in particular it may point to one
	of the $n$ internal nodes or the leaf. On the level of generating functions this implies
	\begin{align*}
		S(z) &= \sum_{n \geq 0} (n+1) r_n \frac{z^{n+1}}{(n+1)!} = z R(z). \qedhere
	\end{align*}
\end{proof}

With the help of this lemma, we are able to construct the generating function
of relaxed trees of right height equal to $0$.
Let $\mathcal{R}_0$ be the respective combinatorial class,
and $R_0(z) = \sum_{n \geq 0} r_{0,n} \frac{z^n}{n!}$ be the associated generating function.

\begin{coro}
	\label{coro:R0}
	The generating function of relaxed trees of right height equal to $0$ is
	\begin{align*}
		R_0(z) &= \frac{1}{1-z}, \qquad
		\text{ and } \qquad
		r_{0,n} = n!.
	\end{align*}
\end{coro}

\begin{proof}
	Such a tree is either just a leaf of size $0$ or it is constructed
	from an element of $\mathcal{R}_0$ by appending a new root node. Obviously,
	this construction does not increase the right height, and it constructs
	all such trees. On the level of generating functions this directly translates into
	\begin{align*}
		R_0(z) &= 1 + z R_0(z).
	\end{align*}
	Solving the equation and extracting coefficients gives the result.
\end{proof}

This gives an alternative proof of the lower bound in Lemma~\ref{lem:compgrowth}. It nicely exemplifies how exponential generating functions model operations on compacted trees.

We proceed now with other operations on combinatorial classes and generating functions. The next
two might seem ``strange'' at first glance, as they do not produce relaxed trees. However, they
are the basic operations for the construction of other ones.

\begin{lemma}[Adding/deleting the root while ignoring pointers]
	\label{lem:adddelnopointer}
	Let $\mathcal{R}$ be a class of relaxed trees. Let $\mathcal{I}$ be the class of objects obtained from
	$\mathcal{R}$ by adding a new root node \emph{without pointer} (as its right child),
	and let $\mathcal{D}$ be the class obtained from $\mathcal{R}$ by deleting the root node but (if existent)
\emph{keeping its pointer}.\footnote{This means in particular, that a single leaf, being root of a
size 0 object, simply disappears. Furthermore, an object with a root having no pointers will
become disconnected at the root. The pointers from the right to the left subtree remain. However,
this construction will only be used when the root has a pointer.} Then,
	\begin{align*}
		I(z) &= \int R(z) \, dz, \\
		D(z) &= \frac{d}{dz} R(z).
	\end{align*}
\end{lemma}

\begin{proof}
	Adding a new root node increases the size by one, whereas deleting it decreases it by one. Hence,
	elements of $\mathcal{R}$ of size $n$ are in bijection with elements of
	$\mathcal{I}$ of size $n+1$ as well as with elements of $\mathcal{D}$ of size $n-1$, compare Figure~\ref{fig:adddel}. Therefore, we get
	\begin{align*}
		I(z) &= \sum_{n \geq 0} r_{n} \frac{z^{n+1}}{(n+1)!} = \int R(z) \, dz, \\
		D(z) &= \sum_{n \geq 1} r_{n} \frac{z^{n-1}}{(n-1)!} = \frac{d}{dz} R(z). \qedhere
	\end{align*}
\end{proof}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.25\textwidth]{newroot}
	\qquad
	\includegraphics[width=0.25\textwidth]{deleteroot}
	\qquad
	\includegraphics[width=0.25\textwidth]{pointing}
	\caption{\small Adding a new root node without pointer, deleting a root
		node while preserving its (possible) pointer,
		and adding a new pointer to the existing root node.}
	\label{fig:adddel}
\end{figure}

These constructions can then be used to derive the following to operations:

\begin{prop}[Sequences and pointers]
	\label{prop:seqpoint}
	The generating function $S(z)$ corresponding to the class obtained by
appending an arbitrary (possibly empty but finite) sequence of nodes to the root (each with one pointer) to a class $\mathcal{R}$ is given by
	\begin{align*}
		S(z) &= \frac{1}{1-z} R(z).
	\end{align*}
	The generating function $P(z)$ of the class obtained by adding a new,
	additional pointer to the root nodes of the objects of a class $\mathcal{R}$ is given by
	\begin{align*}
		P(z) &= z \frac{d}{dz} R(z) + r_0.
	\end{align*}
\end{prop}

\begin{proof}
	This is a direct consequence of the Lemmas~\ref{lem:approot}
	and \ref{lem:adddelnopointer}, compare Figures~\ref{fig:adddel} and \ref{fig:addsequence}.
\end{proof}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.8\textwidth]{appendsequence}
	\caption{\small Appending a finite (possibly empty) sequence to the root node.}
	\label{fig:addsequence}
\end{figure}

Now we have all operations needed to continue our investigation of trees with bounded right height.
In the next sections we show how this calculus is used to derive
differential equations for relaxed and compacted trees of bounded right height.

In the sequel, it will prove convenient to work with operators on generating functions.
For this purpose, we will use the same letters for the operators as were used for
the combinatorial classes (or generating functions)

\section{Relaxed binary trees}
\label{sec:relaxed}

We will now show how to use the calculus developed in Section~\ref{sec:operations}
to derive ordinary differential equations for the exponential generating
functions of relaxed trees of bounded right height.
In this context we introduce the following notation: Let $\mathcal{R}$ be the combinatorial class
of relaxed trees. Its exponential generating function is given by
$R(z) = \sum_{n \geq 0} r_n \frac{z^n}{n!}$ where $r_n$
denotes the number of elements in $\mathcal{R}$ of size $n$.
We denote the class of relaxed trees of right height at most $k$ by $\mathcal{R}_k$
and its corresponding exponential generating function by $R_k(z) = \sum_{n \geq 0} r_{k,n} \frac{z^n}{n!}$.

We have derived $R_0(z)$ in Corollary~\ref{coro:R0} as
\begin{align*}
	R_0(z) &= \frac{1}{1-z} = \sum_{n \geq 0} n! \frac{z^n}{n!}.
\end{align*}

Let us now consider relaxed trees of right height \emph{at most one}.

\subsection{Relaxed trees of right height at most 1}
\label{sec:R1}

Let $\mathcal{R}_1$ be the combinatorial class of relaxed trees with right height at most $1$, compare Figure~\ref{fig:R1l}.
The corresponding generating function is given by $R_1(z) = \sum_{n \geq 0} r_{1,n} \frac{z^n}{n!}$.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.9\textwidth]{R1l}
	\caption{\small A relaxed tree from $\mathcal{R}_1$, i.e.~with right height at most $1$.}
	\label{fig:R1l}
\end{figure}

We will break the problem into smaller parts by decomposing $\mathcal{R}_1$ according to the following equation
\begin{align}
	R_1(z) &= \sum_{\ell \geq 0} R_{1,\ell}(z), \label{eq:R1decomp}
\end{align}
where $R_{1,\ell}(z)$ is the exponential generating function of
relaxed binary trees with exactly $\ell$ right subtrees, i.e.~$\ell$
right edges in the spine going from level $0$ to level $1$.
Obviously, we have $R_{1,0}(z) = R_0(z) = \frac{1}{1-z}$.
In order to get $R_{1,1}(z)$, we apply the previously developed constructions.
An illustration of such a tree is shown in Figure~\ref{fig:R11}.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.6\textwidth]{R11}
	\caption{\small A relaxed tree with exactly one right edge in the spine.}
	\label{fig:R11}
\end{figure}

\begin{prop}
	\label{prop:R11}
	The generating function of relaxed trees with exactly one right edge in the spine is given by
	\begin{align*}
		R_{1,1}(z) &= \frac{1}{1-z} \int{ \frac{1}{1-z} z \left( z R_{1,0}(z)\right)' \, dz}.
	\end{align*}
\end{prop}

\begin{proof}
	The idea is to decompose the structure of $\mathcal{R}_{1,1}$ into smaller parts
	which are in bijection to constructible classes.
	\begin{enumerate}
		\item \label{item:R11a}
		On level $0$ there is a unique node with one right edge, see Figure~\ref{fig:R11}.
Before this node there is a possibly empty sequence of nodes corresponding to the sequence
construction given by the operator $\mathcal{S}$. Call this the initial sequence. First consider a relaxed
tree with empty initial sequence, see Figure~\ref{fig:R11dropseq}.

		\begin{figure}[htb]
			\centering
			\includegraphics[width=0.3\textwidth]{R11dropseq}
			\caption{\small Step~1: An element of $\mathcal{R}_{1,1}$ with empty sequence of
initial nodes on level~$0$.}
			\label{fig:R11dropseq}
		\end{figure}

		\item \label{item:R11b}
		On level $0$, the left child of the unique node with two children (and without pointer)
		is followed by a sequence of nodes, whose pointers may only point to vertices of
the sequence.
		This is an element of $\mathcal{R}_0$ and thus counted by $R_0(z)$.

		Furthermore, we see that the elements on level $1$ form a sequence with a cherry
		as its last element. Its pointers may also point to nodes from the sequence
discussed in the previous paragraph, which is in bijection with $\mathcal{R}_0$.
		By moving the $\mathcal{R}_0$-instance of level $0$ to the end of the sequence on level $1$
		we get a sequence containing one special node which has two pointers.
		Then we delete the last node on level $0$,
		compare with Figure~\ref{fig:R11decompb}.

		In terms of generating functions we get
	\begin{align}
		\hat{R}_{1,0}(z) := \frac{1}{1-z} \underbrace{z\left( z R_{1,0}(z)
\right)'}_{\text{add root with two pointers}}. \label{eq:addrootwith2pointers}
	\end{align}
	Note that due to the cherry every element has at least one internal node.
		%
		\begin{figure}[htb]
			\centering
			\includegraphics[width=0.35\textwidth]{R11decompose}
			\qquad
			\includegraphics[width=0.5\textwidth]{R11deletetopnode}
			\caption{\small Step~2: Nodes of level~$0$ can only point to nodes on level~$0$ (left);
				moving these nodes to level $1$ and deleting the remaining node at level~$0$
				gives $\hat{R}_{1,0}(z)$ (right).}
			\label{fig:R11decompb}
		\end{figure}

		\item
		Furthermore, notice that the node on level $0$ containing a right child (and not a right pointer)
		has no pointers. However, elements of the initial sequence may point to it.
		Therefore, we reinsert this node by adding it as a new root without pointer.
		The constructed object bijectively corresponds to the elements of $\mathcal{R}_{1,1}$ with
empty initial sequence.

		\item
		Finally, we append an initial sequence (cf. Step $1$).
	\end{enumerate}
After those steps, the resulting object looks like shown in Figure~\ref{fig:R11decompfinished}:
a sequence with two special nodes, one having no pointer, the other one having two pointers. The class
of all such elements is in bijection with $\mathcal{R}_{1,1}$, as all the steps above can be reverted.
		%
		\begin{figure}[htb]
			\centering
			\includegraphics[width=0.7\textwidth]{R11decompfinished}
			\caption{\small Step~4: The final sequence-like object bijectively corresponding to $\mathcal{R}_{1,1}$.}
			\label{fig:R11decompfinished}
		\end{figure}

Now we have to translate the operations performed in the four steps into algebraic operations on
generating functions. As already mentioned, after Step 2 the class of objects we get in that
way has generating function $\frac{1}{1-z} z\left( z R_{1,0}(z)\right)'$. The operation in Step
3 corresponds to integrating the generating function by Lemma~\ref{lem:adddelnopointer}. The final
step is the application of the operator $S$ of Proposition~\ref{prop:seqpoint} and therefore
generates a factor $\frac{1}{1-z}$, which completes the proof.
\end{proof}

The main idea of the previous proof was to cut and glue the $\mathcal{R}_{1,1}$-instance in such a way
that a sequence-like object appears such that the process forms a bijection from $\mathcal{R}_{1,1}$ to
the class of sequence-like objects of the form shown in Figure~\ref{fig:R11decompfinished}.
This new object has the advantage of being
constructible by the operations introduced in Section~\ref{sec:operations}.

Of course, one can easily compute $R_{1,1}(z)$ explicitly.
Yet, this representation is easier to generalize to $R_{1,\ell}(z)$.

\begin{coro}
	\label{coro:R1l}
	The generating function of relaxed trees $\mathcal{R}_{1,\ell}$ with exactly $\ell$
	right edges in the spine from level $0$ to level $1$ is given by
	\begin{align*}
		R_{1,\ell}(z) &= \frac{1}{1-z} \int{ \frac{1}{1-z} z \left( z R_{1,\ell-1}(z)\right)' \, dz}, \qquad \ell > 1,\\
		R_{1,0}(z) &= R_0(z) = \frac{1}{1-z}.
	\end{align*}
\end{coro}

\begin{proof}
	By cutting at the first right edge from level~$0$ to level~$1$,
	we observe a decomposition into an initial sequence, a right edge
	from level~$0$ to level~$1$ with its two endnodes being a sequence on level~$1$
	and an instance counted by $R_{1,\ell-1}(z)$.
	The decomposition is exhibited in Figure~\ref{fig:R1lstructure}.
	Thus, we may reuse the construction from Proposition~\ref{prop:R11}
	by replacing the initial value $R_{1,0}(z)$ by $R_{1,\ell-1}(z)$.
\end{proof}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.8\textwidth]{R1lstructure}
	\caption{\small A recursive decomposition of elements from $\mathcal{R}_{1,\ell}$.
		}
	\label{fig:R1lstructure}
\end{figure}
Finally, we are able to combine the previous results to derive
the generating function of~$\mathcal{R}_1$. We need the classical notation of \emph{double factorials}:
\begin{align*}
	n!! &:= \prod\limits_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} (n - 2k), \qquad \text{ for }  n \in \mathbb{N}.
\end{align*}
\begin{theo}
	\label{theo:R1}
	The exponential generating function of relaxed trees of right height at most $1$ is D-finite and satisfies
	\begin{align*}
		(1-2z) R_1'(z) - R_1(z) &= 0, &
		R_1(0)=1.
	\end{align*}
	The closed form formula and the coefficients are given by
	\begin{align*}
		R_1(z) &= \frac{1}{\sqrt{1-2z}}, &
		r_{1,n} &= (2n-1)!!.
	\end{align*}
\end{theo}
\begin{remark}
The general background of $D$-finite functions is well presented in Stanley's book~\cite{stan99}.
\end{remark}
\begin{proof}
	We start with the result of Corollary~\ref{coro:R1l}. But instead of the integral representation, we use the following differential equation valid for $\ell \geq 1$:
	\begin{align*}
		(1-z) \left( (1-z) R_{1,\ell}(z) \right)' =  z\left( z R_{1,\ell-1}(z) \right)'.
	\end{align*}
	Remembering the initial decomposition \eqref{eq:R1decomp} and summing over all $\ell \geq
1$ we get
	\begin{align*}
		(1-z) \left( (1-z) \left( R_1(z) - R_{1,0}(z) \right) \right)' =  z\left( z R_{1}(z) \right)'.
	\end{align*}
	Rearranging this equation and replacing $R_{1,0}(z)$ by $R_0(z)$ we get
	\begin{align}
		(1-2z) R_1'(z) - R_1(z) - (1-z) \left((1-z)R_0(z)\right)' = 0. \label{eq:R1dfinite}
	\end{align}
	%
	Now, $R_0(z) = \frac{1}{1-z}$, hence the differential equation simplifies to
	\begin{align*}
		(1-2z) R_1'(z) - R_1(z) = 0.
	\end{align*}
	Solving this equation by separation of variables yields the closed form expression.
	Finally, the coefficients extraction is easy while using
	$\frac{1}{\sqrt{1-4z}} = \sum_{n \geq 0} \binom{2n}{n} z^n$.
\end{proof}

\subsection{Relaxed trees of right height at most 2}
\label{sec:R2}

Let $\mathcal{R}_2$ be the combinatorial class of relaxed trees with right height at most $2$, compare Figure~\ref{fig:R2}.
The corresponding generating function is given by $R_2(z) = \sum_{n \geq 0} r_{2,n} \frac{z^n}{n!}$.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.9\textwidth]{R2}
	\caption{\small A relaxed tree from $\mathcal{R}_2$, i.e.~with right height at most $2$.}
	\label{fig:R2}
\end{figure}

In the same fashion as before, we will break the problem
into smaller parts by decomposing $\mathcal{R}_2$ into
\begin{align}
	R_2(z) &= \sum_{\ell \geq 0} R_{2,\ell}(z), \label{eq:R2decomp}
\end{align}
where $R_{2,\ell}(z)$ is the exponential generating function of relaxed trees of right height
at most~$2$ with exactly $\ell$ right edges in the spine
going from level $0$ to level $1$. Obviously, we have $R_{2,0}(z) = R_0(z) = \frac{1}{1-z}$.

\begin{remark}\label{rem:incond}
Note that, as seen in the sequel, the functions $R_{k,0}(z)=\frac{1}{1-z}$ are in fact the
perturbation of the recurrence of differential equations we are currently building. Moreover, they
also uniquely determine the initial condition of this recurrence. Therefore, we will sloppily call
these functions as well as others in the same role ``initial conditions''. This should not be
confused with the initial conditions of the differential equations themselves. Those do not play
any role in our arguments, so the risk of confusion should be low.
\end{remark}

\begin{prop}
	\label{prop:R21}
	The exponential generating function of relaxed trees of right height at most~$2$
	with exactly one right edge from level $0$ to level $1$ in the spine satisfies
	\begin{align}
		(1-2z) \left( (1-z) R_{2,1}(z) \right)''
			- \left( (1-z) R_{2,1}(z) \right)'
			- \left( z ( zR_{2,0}(z) )' \right)' = 0. \label{eq:R21dfinite}
	\end{align}
\end{prop}

\begin{proof}
	The main idea is to decompose the structure of $\mathcal{R}_{2,1}$ again into $4$ parts
	(compare with Figure~\ref{fig:R21decomp}): an initial sequence, the first right edge
	from level $0$ to level $1$, the sequence on level $0$ after this right edge,
	and an instance of $\mathcal{R}_{1}$ starting on level $1$ after this right edge.
	Then we use the same transformation idea as in the proof of Proposition~\ref{prop:R11}.
	We take the sequence on level $0$ after the right edge and move it to the
	end of the $\mathcal{R}_1$-instance. Note that this is legitimate concerning the pointers.
	But it generates a node with two pointers within a sequence of $\mathcal{R}_1$.
	With respect to the $\mathcal{R}_1$-instance this change happens on its top level to the very left.

	We can now delete the initial sequence and the level $0$ node of the right edge,
	as they can be created again by known operations.
	Let us denote the class of objects obtained performing the above operations on objects
from $\mathcal{R}_2$ and then deleting these two parts by $\mathcal F$, its generating function by $F(z)$.
	By Lemma~\ref{lem:adddelnopointer} and Proposition~\ref{prop:seqpoint} we get
	\begin{align*}
		F(z) &= ((1-z) R_{2,1}(z))'.
	\end{align*}

	Note that $F(z)$ is associated to structures with right height at most $1$.
	It is nearly an instance of $\mathcal{R}_1$. There are only two differences:

	First, it has a special construction after its last right edge.
	With respect to the differential equation~\eqref{eq:R1dfinite} which corresponds to
	the class $\mathcal{R}_1$, this change affects the initial condition (recall Remark~\ref{rem:incond}!) $\mathcal{R}_0$.
	Thus, we can reuse this specification, by replacing the initial condition.
	On the level of generating functions this corresponds to replacing $R_0(z)$ by $\frac{1}{1-z} (z R_{2,0}(z))'$, because a (possibly empty) sequence
	is followed by a node with a double pointer and another sequence (compare with Figure~\ref{fig:R11decompb}).
	Hence, by~\eqref{eq:R1dfinite} the corresponding combinatorial class $\mathcal G$ has
generating function $G(z)$ given by
	\begin{align*}
		(1 &-2z)G'(z) - G(z) - (1-z) ((1-z)G_0(z))' = 0, \quad \text{ with } \quad
		G_0(z) = \frac{1}{1-z} (z R_{2,0}(z))'.
	\end{align*}

	Second, due to the unique right edge from level $0$ to level $1$, every object in
$\mathcal F$
	has at least one node. The elements in $\mathcal G$ which do not satisfy this condition
are leaves and they belong to $\mathcal G_0$. On the level of generating functions the elements of
$\mathcal G_0$ which are not leaves correspond to $zG_0(z)$, as $\mathcal G_0$ is a sequence construction. This gives
	\begin{align*}
		F(z) &= G(z) - (1-z) G_0(z).
	\end{align*}
	This yields
	\begin{align}
		G(z) &= \left( (1-z) R_{2,1}(z) \right)' + (z R_{2,0}(z))'. \label{eq:Gexpressed}
	\end{align}
	Finally, putting everything together some tedious calculations show \eqref{eq:R21dfinite}.
\end{proof}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.6\textwidth]{R21decomposition}
	\caption{\small Transforming a structure of $\mathcal{R}_{2,1}$ into an instance of $\mathcal{R}_{1}$.}
	\label{fig:R21decomp}
\end{figure}

\begin{remark}
	We want to comment on the last reasoning in the previous proof.
	It might seem complicated and awkward to delete the leaf by subtracting
	$G_0(z)$ and adding the shifted version $zG_0(z)$.
	Another solution would obviously be to subtract only the generating function associated
with a single leaf, giving $F(z) = G(z) - 1$. This is of course legitimate,
	however it leads to an inhomogeneous differential equation.
	We will see that it is crucial to have a homogeneous equation,
	because we want to sum over infinitely many of them.
\end{remark}
As in the $R_{1,\ell}(z)$ case, we get $R_{2,\ell}(z)$ for $\ell \geq 2$
by a recursive application of the previous arguments.

\begin{coro}
	\label{coro:R2l}
	The generating function of relaxed trees with right height at most $2$,
	and exactly $\ell$ right edges in the spine from level $0$ to level $1$ is given by
	\begin{align*}
		&(1-2z) \left( (1-z) R_{2,\ell}(z) \right)''
			- \left( (1-z) R_{2,\ell}(z) \right)'
			- \left( z ( zR_{2,\ell-1}(z) )' \right)' = 0, \qquad \ell > 1,\\
		&R_{1,0}(z) = R_0(z) = \frac{1}{1-z}.
	\end{align*}
\end{coro}

\begin{proof}
	By cutting at the first right edge from level $0$ to level $1$,
	we observe a decomposition into an initial sequence, a right edge
	from level $0$ to level $1$ with $2$ nodes, a sequence on level~$1$
	and an instance counted by $R_{2,\ell-1}(z)$.
	Thus, we may reuse the construction from the proof of Proposition~\ref{prop:R21}
	by replacing the initial value $R_{2,0}(z)$ with $R_{2,\ell-1}(z)$.
\end{proof}
Note that for the final result it is crucial that we found homogeneous differential equations.

\begin{theo}
	\label{theo:R2}
	The exponential generating function of relaxed trees of right height at most $2$
	is D-finite and satisfies
	\begin{align*}
		(z^2-3z+1) R_2''(z) + (2z-3) R_2'(z) &= 0, &
		R_2(0)=1,~R_2'(0)=1.
	\end{align*}
	A closed form formula and the coefficients are given by
	\begin{align*}
		R_2(z) &= -\frac{2}{\sqrt{5}} \artanh \left( \frac{2z-3}{\sqrt{5}} \right)
							- \frac{1}{\sqrt{5}}\left( \log \left( \frac{7 + 3\sqrt{5}}{2} \right) - \pi i \right), \\
		r_{2,n} &= \frac{(n-1)!}{\sqrt{5}} \left( \left( \frac{3 + \sqrt{5}}{2} \right)^n - \left( \frac{3 - \sqrt{5}}{2} \right)^n \right).
	\end{align*}
\end{theo}

\begin{proof}
	Again, let us take the result of Corollary~\ref{coro:R2l} and
	sum over all $\ell \geq 1$, while remembering the decomposition
	\eqref{eq:R2decomp}. By linearity this gives
	\begin{align}
		(1-2z) \left( (1-z) (R_2(z) - R_{2,0}(z) ) \right)''
			- \left( (1-z) (R_2(z) - R_{2,0}(z) ) \right)'
			- \left( z ( zR_2(z) )' \right)' = 0. \label{eq:R2subst}
	\end{align}
	A simplification gives
	\begin{align*}
		(z^2-3z+1) R_2''(z)
			+ (2z-3) R_2'(z)
			- (1-2z)((1-z)R_{2,0}(z))'' + ((1-z) R_{2,0}(z) )' = 0.
	\end{align*}
	Inserting the initial value $R_{2,0}(z) = \frac{1}{1-z}$ we get the D-finite expression.
	The correctness of the closed form formula can then be easily checked
	with a computer algebra system.

	In order to extract the coefficients of $R_2(z)$ we observe that the differential
	equation can be simplified further by an integration with respect to $z$.
	Thus, it is equivalent to
	\begin{align*}
		(z^2+3z+1) R_2'(z) &=1, &
		R_2(0) = 1,
	\end{align*}
	as $R_2'(0)=1$. Next, observe that as we are dealing with exponential
	generating functions, the derivative is just a shift on the level of coefficients.
	In other words, $[z^n] R_2(z) = [z^{n-1}] R_2'(z)$.
	Therefore, a partial fraction decomposition enables a direct extraction of the coefficients.
\end{proof}

\subsection{Relaxed trees of right height at most \texorpdfstring{$k$}{k}}
\label{sec:relaxedheightk}

The approach from the previous section can be generalized to an arbitrary bound $k\ge 2$ for the
right height. Let $R_k(z) = \sum_{n \geq 0} r_{k,n} \frac{z^n}{n!}$ be the corresponding
generating function. The idea is to use the previous construction, and to derive a differential equation for $R_k(z)$ from the one of $R_{k-1}(z)$.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.8\textwidth]{R3}
	\caption{\small A relaxed tree from $\mathcal{R}_3$, i.e.~with right height at most $3$.}
	\label{fig:R3}
\end{figure}

We introduce a family of linear differential operators $L_k$, $k \geq 1$, which describe the
differential equations constructed for $R_k(z)$. Let $D$ denote the differential operator
$\frac{d}{dz}$ and $1$ the identity operator, i.e. $1 \cdot F(z)=F(z)$. For example, $(D \cdot z) (F(z)) = \frac{d}{dz} \left( z F(z) \right)$.
\begin{theo}[Differential operators]
	\label{theo:diffoprelaxed}
	Let $(L_k)_{k \geq 0}$ be a family of differential operators given by
	\begin{align*}
		L_0 &= (1-z) \cdot 1,\\
		L_1 &= (1-2z) D - 1, \\
		L_{k} &= L_{k-1} \cdot D - L_{k-2} \cdot D^2 z, \qquad k \geq 2.
	\end{align*}
	Then the exponential generating function $R_k(z)$ of relaxed binary trees with right height at most $k$ satisfies for $k \geq 1$
	\begin{align}\label{mainODE}
		L_k \cdot R_k(z) &= 0.
	\end{align}
\end{theo}

\begin{proof}
	For $k \geq 1$ we derive two families of operators:
	The differential operator $L_k$ and an auxiliary operator $H_k$ for the inhomogeneity such that
	\begin{align*}
		L_k \cdot R_k(z) &= H_k \cdot R_0(z).
	\end{align*}
	For $k=1$ we derived in~\eqref{eq:R1dfinite} the claimed form $L_1 \cdot R_1(z) = H_1
\cdot R_0(z)$ with $H_1 = L_0 D (1-z)$.

	We continue with the case $k=2$. The explicit differential operator is given in Theorem~\ref{theo:R2}. We will now show how the operator can be constructed from the ones for $R_1(z)$ and $R_0(z)$ in the language of operators.

	In Proposition~\ref{prop:R21} we have derived the necessary
	substitution to get the differential equation of $R_2(z)$
	from the one of $R_1(z)$. The idea was to decompose $\mathcal{R}_2$ with respect to the number $\ell$
	of right edges from level $0$ to level $1$, see Figure~\ref{fig:R21decomp}.
	This transformation creates an $\mathcal{R}_1$-like structure with a new initial condition $G_{0,\ell}(z)$ and the constraint not to be empty.

	From~\eqref{eq:R1dfinite} we get the generic differential equation for $\mathcal{R}_1$-like structures with generating function $G_{\ell}(z)$ as
	\begin{align*}
		L_1 \cdot G_{\ell}(z) = H_1 \cdot G_{0,\ell}(z).
	\end{align*}

	First, the new initial condition is given by
	\begin{align*}
		G_{0,\ell}(z) &= \left(\frac{1}{1-z} D z\right) \cdot R_{2,\ell-1}(z).
	\end{align*}
	Second, the $\mathcal{R}_1$-like class being in bijection to $\mathcal{R}_{2,\ell}$ cannot be empty, and the initial sequence on level $0$ has to be appended. Thus, the substitution~\eqref{eq:Gexpressed} has to be used where $R_{2,1}(z)$ is replaced by $R_{2,\ell}(z)$, and $R_{2,0}(z)$ by $R_{2,\ell-1}(z)$. This gives for $\ell \geq 1$
	\begin{align*}
		L_1 \left( (D (1-z)) \cdot  R_{2,\ell}(z) + (D z) \cdot R_{2,\ell-1}(z)
\right) - H_1\left( \left(\frac{1}{1-z} D z\right) \cdot R_{2,\ell-1}(z) \right) = 0.
	\end{align*}
	Summing over $\ell \geq 1$ and recalling that $R_2(z) = \sum_{\ell \geq 0} R_{2,\ell}(z)$ we get
	\begin{align*}
		L_1 \cdot D \cdot R_2(z) - L_0 \cdot D^2 \cdot z \cdot R_2(z) = L_1 \cdot D \cdot (1-z) \cdot R_{2,0}(z).
	\end{align*}
	On the left we see the differential operator $L_2$ applied to $R_2(z)$ and on the right the inhomogeneity operator $H_2$ applied to $R_{2,0}(z)$.
	Inserting $R_{2,0}(z) = \frac{1}{1-z}$ shows the claim for $k=2$.

	Finally, for larger $k$, we can recycle the previous arguments for $k=2$
	and apply them recursively. This holds, as we may again cut an instance of $\mathcal{R}_k$
	 at the first right edge in the spine from level $0$ to level $1$ and decompose
	it in the repeatedly shown fashion, compare with Figure~\ref{fig:R21decomp}.
	Then the same reasoning as in Section~\ref{sec:R2} allows us to extract
	the differential equation of $R_k(z)$ from the one of $R_{k-1}(z)$ by
	\begin{align}
		L_{k} &= L_{k-1} \cdot D - H_{k-1} \cdot \frac{1}{1-z} \cdot D \cdot z, &
		H_{k} &= L_{k-1} \cdot D \cdot (1-z). \label{eq:relLHk}
	\end{align}
	Hence, by induction the claim holds.
\end{proof}

Let us apply the last theorem and compute the first few differential equations.
\begin{equation*}
	(1-2z) \frac{d}{dz} R_1(z) - R_1(z) = 0,
\end{equation*}
\begin{equation*}
	(z^2 - 3z + 1) \frac{d^{2}}{dz^{2}} R_2(z) + (2z-3) \frac{d}{dz} R_2(z) = 0,
\end{equation*}
\begin{equation*}
	(3z^2-4z+1) \frac{d^{3}}{dz^{3}} R_3(z) + (9z-6) \frac{d^{2}}{dz^{2}}R_3(z) + 2 \frac{d}{dz} R_3(z) = 0,
\end{equation*}
\begin{equation*}
	-(z^3-6z^2+5z-1) \frac{d^{4}}{dz^{4}} R_4(z) - (6z^2-24z+10) \frac{d^{3}}{dz^{3}} R_4(z) - (6z-11) \frac{d^{2}}{dz^{2}} R_4(z) = 0.
\end{equation*}
The initial conditions of the differential equations can be obtained successively from lower order solutions.
In particular, note that due to the construction the first $k+1$ coefficients of $R_k(z)$
are the first $k+1$ elements of the counting sequence of relaxed trees, as a tree of size $k+1$
has always right height at most $k$. Thus with $R_k(z)$ we can enumerate all relaxed trees up to size $k+1$.

Next, we take a closer look at these operators.

\begin{theo}[Properties of $L_k$]
	\label{theo:Dkprop}
	For any $k \in \mathbb{N}$, let $L_k$ be as in Theorem~\ref{theo:diffoprelaxed}. Let $\ell_{k,i}(z) \in \mathbb{C}[z]$ be such that
	\begin{align}\label{operater_L_k}
		L_k &= \ell_{k,k}(z) D^k
						+ \ell_{k,k-1}(z) D^{k-1}
						+ \ldots
						+ \ell_{k,0}(z).
	\end{align}
	Then we have
	\begin{align*}
		\ell_{k,0}(z) &= 0, \\
		\ell_{k,1}(z) &= \ell_{k-1,0}(z) - 2 \ell_{k-2,0}(z),\\
		\ell_{k,i}(z) &= \ell_{k-1,i-1}(z) - (i+1) \ell_{k-2,i-1}(z) - z \ell_{k-2,i-2}(z), \qquad 2 \leq i \leq k-1,\\
		\ell_{k,k}(z) &= \ell_{k-1,k-1}(z) - z \ell_{k-2,k-2}(z).
	\end{align*}
	The initial polynomials are $\ell_{0,0}(z) = 1-z$, $\ell_{1,0}(z) = -1$, and $\ell_{1,1}(z) = 1-2z$.
\end{theo}

\begin{proof}
	The initial polynomials are given by Theorem~\ref{theo:diffoprelaxed}. The shape
\eqref{operater_L_k} of the operator $L_k$ follows by induction using its recursive definition.
Using an ansatz and comparing coefficients gives the recurrence relations for $\ell_{k,i}(z)$.
\end{proof}

The asymptotic behavior (according to $n$)
of the number $r_{k,n}$ of relaxed trees with right height at most $k$
is governed by these differential equations.
These differential equations belong to a known class~\cite[Chapter VII.9]{flaj09}. Consider an ordinary generating function of the kind
\begin{align}
	\label{eq:difeqmerogen}
	D^r Y(z) + a_1(z) D^{r-1} Y(z) + \cdots + a_r(z) Y(z) = 0,
\end{align}
where the $a_i \equiv a_i(z)$ are meromorphic in a simply connected domain $\Omega$. Given a meromorphic function $f(z)$, let $\omega_{\zeta}(f)$ be the order of the pole of $f$ at $\zeta$, and $\omega_\zeta(f)=0$ meaning that $f(z)$ is analytic at $\zeta$.

\begin{definition}[Regular singularity, {\cite[p.~519]{flaj09}}]
	\label{def:regularsing}
	The differential equation~\eqref{eq:difeqmerogen} is said to have a singularity at $\zeta$ if at least one of the $\omega_\zeta(f)$ is positive. The point $\zeta$ is said to be a \emph{regular singularity} if
	\begin{align*}
		\omega_\zeta(a_1) \leq 1, \qquad \omega_\zeta(a_2) \leq 2, \qquad \ldots, \qquad \omega_\zeta(a_r) \leq r,
	\end{align*}
	and an \emph{irregular singularity} otherwise.
\end{definition}

\begin{definition}[Indicial polynomial, {\cite[p.~520]{flaj09}}]
	\label{def:indicialpoly}
	Given an equation of the form~\eqref{eq:difeqmerogen} and a regular singular point $\zeta$, the \emph{indicial polynomial} $I(\alpha)$ at $\zeta$ is defined as
	\begin{align*}
		I(\alpha) &= \alpha^{\underline{r}} + \delta_1 \alpha^{\underline{r-1}} + \cdots + \delta_r, & \text{ where } &&
		\alpha^{\underline{\ell}} &:= \alpha(\alpha-1)\cdots(\alpha-\ell+1)
	\end{align*}
	and $\delta_i := \lim_{z \to \zeta} (z-\zeta)^i a_i(z)$. The \emph{indicial equation at $\zeta$} is the algebraic equation $I(\alpha) = 0$.
\end{definition}

The following technical lemma will be needed to derive the asymptotics for the solutions of the special type of differential equations given in Theorem~\ref{theo:odeasymptregsing}.

\def\ff#1#2{#1^{\underline{#2}}}
\let\set\mathbb

\begin{lemma}
\label{lem:structuresimplefactor}
Let $p_0,\dots,p_r\in\set C[x]$ and consider the differential operator
\[
 L = p_r D^r + \cdots + p_1 D + p_0.
\]
Suppose that $x$ is a simple factor of~$p_r$, and suppose
that for some $\alpha\in\set C$, a solution of $L f(x) = 0$ admits a generalized
series solution $f(x)=\sum_{n\in\alpha+\set Z} c_n x^n$.
Then the coefficient sequence $(c_n)_{n\in\alpha+\set Z}$ satisfies a recurrence of the form
\begin{center}
\begin{tabular}{rll}
$\Bigl(([x^1]p_r)(n-r+1)+  ([x^0]p_{r-1})\Bigr)$ & $\ff{n}{r-1} \; c_{n}$ & \\
  $+ \quad[\cdots]$ & $\ff{(n-1)}{r-2} \; c_{n-1}$ & \\
  $+ \quad[\cdots]$ & $\ff{(n-2)}{r-3} \; c_{n-2}$ & \\
  $+ \quad \dots~$ & & \\
  $+ \quad[\cdots]$ & $c_{n-s}$ & $= \quad 0,$
\end{tabular}
\end{center}
where $[\cdots]$ are certain polynomials in~$n$ and $s$ is some fixed nonnegative integer.
\end{lemma}

\begin{proof}
We have $x^j D^i f = \sum_{n\in\alpha+\set Z} c_n \ff ni x^{n-i+j} = \sum_{n\in\alpha+\set Z} c_{n+i-j} \ff{(n+i-j)}i x^n$
for all $i, j\in\set N$.\\
Write $p_i = \sum_j p_{i,j}x^j$ for $i=0,\dots,r$, in the understanding that $j$ runs through all integers,
but $p_{i,j}$ is zero for all negative and almost all positive indices~$j$. By assumption, we know
that $p_{r,0}=0\neq p_{r,1}$.

It follows that $p_i D^i f = \sum_{n\in\alpha+\set Z} \sum_j p_{i,j} c_{n+i-j} \ff{(n+i-j)}i x^n$ for $i=0,\dots,r$. Then
\[
 L f = \sum_{n\in\alpha+\set Z} \sum_{i=0}^r\sum_j p_{i,j} c_{n+i-j} \ff{(n+i-j)}i x^n = 0
\]
implies, by comparing the coefficients of~$x^n$,
\begin{equation}\label{eq:de2re}
0 = \sum_{i=0}^r\sum_j p_{i,j} c_{n+i-j} \ff{(n+i-j)}i
= \sum_j \sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i c_{n-j}
\end{equation}
for all $n\in\alpha+\set Z$.

Consider a fixed $j\in\set Z$. From the definition $\ff{(n-j)}i=(n-j)(n-j-1)\cdots(n-j-i+1)$ it follows
that $\ff{(n-j)}i\mid\ff{(n-j)}{i+1}$ for every $i\in\set N$.
Therefore, if $k$ is minimal such that $p_{k,k+j}\neq0$, then $\ff{(n-j)}k\mid \sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i$.

Note also that for each fixed $j$, the polynomial $\sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i$ is non-zero if and only if
at least one of the coefficients $p_{i,i+j}$ are non-zero, because the falling factorials form a basis of the vector space
of polynomials.

For $j<-r$, we have $i+j<0$ for all $i=0,\dots,r$, and therefore $p_{i,i+j}=0$ for all $i$ and $\sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i=0$.
Therefore there are no terms $c_{n-j}$ with $j<-r$ present in equation~\eqref{eq:de2re}.

For $j=-r$, we have $i+j<0$ for all $i=0,\dots,r-1$, and therefore $p_{i,i+j}=0$ for all these~$i$.
In addition, we have $p_{r,r-r}=p_{r,0}=0$ by assumption, so again $\sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i=0$,
and no term $c_{n-j}$ with $j=-r$ is present in equation~\eqref{eq:de2re}.

Next, for $j=-r+1$ we have $p_{r,r+(-r+1)}=p_{r,1}\neq0$ by assumption, so the term $c_{n-(r-1)}$ \emph{does}
occur in equation~\eqref{eq:de2re}.
Moreover, since $p_{i,i+(-r+1)}=0$ for all $i<r-1$, we have $\sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i=p_{r,1}\ff{(n-j)}r +
p_{r-1,0}\ff{(n-j)}{r-1}=(p_{r,1}n + p_{r-1,0})\ff{(n+r-1)}{r-1}$.

In general, for any $j>-r+1$, we have $p_{i,i+j}=0$ for all $i<-j$ and therefore $\ff{(n-j)}{-j}\mid\sum_{i=0}^r p_{i,i+j}\ff{(n-j)}i$.
(The understanding here is that $\ff{(n-j)}{-j}=1$ if $-j$ is not positive.)
Substituting $n-r+1$ for~$n$, we have shown the stated form of the recurrence.
\end{proof}

If $\zeta$ is a regular singularity of a differential equation, then all solutions of the differential equation behave for $z\to\zeta$ like $(z-\zeta)^\alpha\log(z-\zeta)^\beta$ for some $\alpha\in\mathbb{C},\beta\in\mathbb{N}$.
The exponents $\alpha$ are roots of the indicial polynomial, and the exponents of the logarithmic terms are related to multiple roots of the indicial polynomial and roots at integer distances. More precisely, in our case the following theorem will be applicable. It is a variant of \cite[Theorem~VII.9]{flaj09} which works due to $\omega_{\zeta}(a_i) = 1$ for all $i=1,\ldots,r$.

\begin{theo}
	\label{theo:odeasymptregsing}
	Consider the differential equation~\eqref{eq:difeqmerogen} and a
	regular singular point $\zeta$ such that $\omega_{\zeta}(a_i) = 1$
	for all $i = 1,\ldots,r$, and $\delta_1 := \lim_{z \to \zeta} (z-\zeta) a_1(z) \geq 0$.
	Then, the vector space of all analytic solutions defined in a slit neighborhood
	of $\zeta$ has a basis of $r$ functions, where $r-1$ functions are of the form
	\begin{align*}
		&(z - \zeta)^{m} H_m(z-\zeta), & m&=0,1,\ldots,r-2,
	\end{align*}
	with functions $H_m$ being analytic at $0$ and satisfying $H_m(0) \neq 0$.
	%
	The $r$-th basis function depends on $\delta_1$:
	\begin{enumerate}
		\item For $\delta_1 \in \{0,1,\ldots,r-1\}$ it is of the form
		\begin{align*}
			(z - \zeta)^{r-1-\delta_1} H(z-\zeta) \log(z-\zeta);
		\end{align*}
		%
		\item For $\delta_1 \in \{r,r+1,\ldots\}$ it is of the form
		\begin{align*}
			(z - \zeta)^{r-1-\delta_1} H(z-\zeta) + H_0(z-\zeta)\left(\log(z-\zeta)\right)^k, \quad \text{ with } \quad k \in \{0,1\};
		\end{align*}
		%
		\item For $\delta_1 \not\in {\mathbb Z}$ it is of the form
		\begin{align*}
			(z - \zeta)^{r-1-\delta_1} H(z-\zeta);
		\end{align*}
	\end{enumerate}
		where $H$ is analytic at $0$, with $H(0) \neq 0$.
\end{theo}

\begin{proof}
	Due to $\omega_{\zeta}(a_i) = 1$ we get by the definition of the
	indicial polynomial that $\delta_i=0$ for $i \geq 2$. Hence, it is given by
	\begin{align*}
		I(\alpha) &= \alpha^{\underline{r}} + \delta_1 \alpha^{\underline{r-1}} = \alpha^{\underline{r-1}} (\alpha-r+1+\delta_1).
	\end{align*}
	Therefore, the roots are $0,1,\ldots,r-2$, and $r-1-\delta_1$.

	Let us treat the consecutive range of roots $0,1,\ldots,r-2$ first.
	Consider the equivalent recurrence relation for the coefficients
	$(c_n)_{n\in \mathbb{N}}$ of the series solution expanded at $\zeta$. It has the form
	\begin{align*}
		I(n) y_n = \Phi(y_{n-1},\ldots,y_{n-N}),
	\end{align*}
	where $I(n)$ is the indicial polynomial, $N=\max_i(r-i+\deg(a_i(z)))$,
	and $\Phi$ is a linear operator with polynomial coefficients in $n$.
	Let $\alpha$ be a root of the indicial polynomial, and consider the sequence
	$(c_n)_{n\in \mathbb{N}}$ extended to ${\mathbb Z}$ with $c_n = 0$ for $n<\alpha$ for $\alpha = 0,1,\ldots,r-2$.
	At $n=\alpha$ we have
	\begin{align}
		\label{eq:birthcoeff}
		0 \cdot y_{\alpha} = \Phi(0,\ldots,0).
	\end{align}
	Hence, $y_{\alpha}$ can be chosen arbitrarily. By Lemma~\ref{lem:structuresimplefactor}, for each choice the recurrence uniquely extends the sequence towards $+\infty$. Therefore, each root $\alpha$ gives rise to a different solution of our recurrence relation. The set of all these solutions is linear independent.
	The consecutive range of zeros implies that the  values $y_{0},\ldots,y_{r-2}$ can be chosen arbitrarily, as they do not interfere with each other. Such a situation does not give rise to any logarithmic terms.

	Next, let us treat the remaining basis solution associated to $r-1-\delta_1$.

	In the first case, there is a multiple root of order $2$. Then, the classical theory of linear differential equations implies the appearance of logarithmic terms, see \cite{henr77,waso87,ince44,SchlesingerI1968}.

	In the second case, the situation is analogous to~\eqref{eq:birthcoeff}: The solution starts to exist at $n=r-1-\delta_1$. But this solution then needs to be continued further, and at $n=0$, we might have a problem. Then, there could emerge a logarithmic term or not.
	This depends on the specific problem.
	If the solution cannot be extended, then a logarithmic factor multiplied
	with the solution at $n=0$ is added, see \cite{ince44}.

	In the third case, the root does not interfere with the other solutions,
	as the difference with any other root is not an integer.
	Thus, it can be continued without problems, and has the claimed form.
\end{proof}

By Theorem~\ref{theo:diffoprelaxed} the differential equations associated to relaxed trees
are of the kind~\eqref{eq:difeqmerogen}.
The roots of the leading term are under these conditions
responsible for the singularities of the solutions.
The dominant one is as usual the one closest to the origin.
Our first aim is to show that for every bounded right height
there exists a unique dominant singularity.
For this purpose we start with the analysis of the polynomials $l_{k,i}(z)$.
They are strongly connected to a famous family of polynomials:
the \emph{Chebyshev polynomials}, see, e.g.,~\cite[Chapter~18]{NIST:DLMF} or \cite[Chapter~22]{AbramowitzStegun1964}.

\begin{definition}[Chebyshev polynomials]
	The \emph{Chebyshev polynomials of the first kind} $T_n(z)$ are defined by the recurrence relation
	\begin{align*}
		T_0(z) &= 1,\\
		T_1(z) &= z, \\
		T_{n+2}(z) &= 2z T_{n+1}(z) - T_{n}(z).
	\end{align*}
	The \emph{Chebyshev polynomials of the second kind} $U_n(z)$ are defined by the recurrence relation
	\begin{align*}
		U_0(z) &= 1,\\
		U_1(z) &= 2z, \\
		U_{n+2}(z) &= 2z U_{n+1}(z) - U_{n}(z).
	\end{align*}
\end{definition}

\begin{lemma}[Transformed leading coefficient]
	\label{lem:chebyshev}
	Let $\ell_{k,i}(z)$ be the coefficients of the operator $L_k$ from Theorem~\ref{theo:Dkprop}.
	Then, for the leading coefficient we get
	\begin{align*}
		\ell_{k,k}(z) &= z^{\frac{k+2}{2}} U_{k+2}\left(\frac{1}{2 \sqrt{z}}\right)
		               = \sum_{n = 0}^{\lfloor \frac{k+2}{2} \rfloor} (-1)^n \binom{k+2-n}{n} z^n,
	\end{align*}
	where $U_k(z)$ are the Chebyshev polynomials of the second kind.
\end{lemma}

\begin{proof}
		We start with the recurrence relation of $\ell_{k,k}(z)$ from Theorem~\ref{theo:Dkprop}.
		Replacing $z$ by $\frac{1}{4z^2}$ and multiplying by $(2x)^{k+2}$, we get
		\begin{align*}
			(2z)^{k+2} \ell_{k,k}\left(\frac{1}{4z^2}\right) =
				2z \cdot (2z)^{k+1} \ell_{k-1,k-1}\left(\frac{1}{4z^2}\right)
				- (2z)^{k} \ell_{k-2,k-2}\left(\frac{1}{4z^2}\right),
		\end{align*}
		and we recognize the recurrence relation for the Chebyshev polynomials of the second kind for $(2z)^{k} \ell_{k-2,k-2}\left(\frac{1}{4z^2}\right)$,  see~\cite[Section~18.9]{NIST:DLMF}.
		Transforming the initial conditions, gives $U_2(z)$ and $U_3(z)$ respectively.

		The closed form is derived from the well-known formula
		$U_k(z) = \sum_{n = 0}^{\lfloor \frac{k}{2} \rfloor} (-1)^n \binom{k-n}{n} z^n$.
\end{proof}

We will also need the following result on $\ell_{k,k-1}(z)$. Its structure is directly related to the one of $\ell_{k,k}(z)$.

\begin{lemma}[Transformed $\ell_{k,k-1}(z)$]
	\label{lem:lkk1}
	For the coefficient $\ell_{k,k-1}(z)$ of the operator $L_k$ from Theorem~\ref{theo:Dkprop},
	we get
	\begin{align*}
		\ell_{k,k-1}(z) &= \frac{k}{2} \ell'_{k,k}(z),
	\end{align*}
	for $k \geq 1$ and $|z| < \rho_k$.
\end{lemma}

\begin{proof}
  By Theorem~\ref{theo:Dkprop} the claim holds for $k =1$ and $k=2$. We proceed by induction. Assume the claim holds for $1 \leq i \leq k$. Then, differentiating both sides of the defining equation of $\ell_{k,k}(z)$ given in Theorem~\ref{theo:Dkprop} we get
	\begin{align*}
		\ell'_{k,k}(z) &= \ell'_{k-1,k-1}(z) - z \ell'_{k-2,k-2}(z) - \ell_{k-2,k-2}(z).
	\end{align*}
	Next, we apply the induction hypothesis and get
	\begin{align*}
		\ell'_{k,k}(z) &= \frac{2}{k-1} \ell_{k-1,k-2}(z) - z \frac{2}{k-2} \ell_{k-2,k-3}(z) - \ell_{k-2,k-2}(z).
	\end{align*}
	Finally, by rearranging the equation and utilizing the defining recurrence relation for $\ell_{k,k-1}(z)$ we prove (omitting the arguments)
	\begin{align*}
							\ell'_{k,k}	&= \frac{2}{k} \Big(\underbrace{ \ell_{k-1,k-2} - z \ell_{k-2,k-3} - k \ell_{k-2,k-2} }_{= \ell_{k,k-1}} \Big)
								+ \frac{1}{k} \Big(\underbrace{ \ell_{k-1,k-1} - 2z \ell'_{k-2,k-2} + k \ell_{k-2,k-2} }_{= 0 }\Big),
	\end{align*}
	where the last expression is equal to $0$, as we know the polynomial $\ell_{k,k}(z)$ explicitly from Lemma~\ref{lem:chebyshev}.
\end{proof}

Chebyshev polynomials are well-studied objects.
We summarize some important results (for our analysis) in the following lemma.
\begin{lemma}
	\label{lem:lkkproperties}
	The roots of $\ell_{k,k}(z)$ are real, positive, and distinct.
	Let $\rho_k$ be the smallest real root of $\ell_{k,k}(z)$. Then, we have
	\begin{align*}
		\rho_k &= \frac{1}{4\cos^2\left(\frac{\pi}{k+3}\right)}.
	\end{align*}
	Furthermore, $\rho_k$ is not a root of $\ell_{k,k-1}(z)$.
\end{lemma}

\begin{proof}
	The results follow from the well-known results on Chebyshev polynomials~\cite[Section~18.5]{NIST:DLMF}.
	In particular, the roots $x_{k,j}$ of $U_k(z)$ admit the closed form expressions
	\begin{align*}
		x_{k,j} &= \cos\left(\frac{j \pi}{k+1}\right).
	\end{align*}
	This implies the closed form expression of $\rho_k$.
	The last result follows from the closed form expression of $\ell_{k,k-1}(z)$ from Lemma~\ref{lem:lkk1} and the fact that the roots of Chebyshev polynomials are all simple.
\end{proof}

With this information, we are finally able to characterize the indicial polynomials.

\begin{prop}
	\label{prop:indicialpoly}
	The indicial polynomial $I_k(\alpha)$ of the $k$-th differential equation is given by $I_k(\alpha) = \alpha^{\underline{k-1}} (\alpha-(\frac{k}{2}-1))$.
\end{prop}

\begin{proof}
	By Definition~\ref{def:indicialpoly} we need to show that $\delta_i=0$ for $i \geq 1$ and $\delta_1 = \frac{k}{2}$. The first claim holds by Lemma~\ref{lem:lkkproperties}, as $\ell_{k,i}(z)/\ell_{k,k}(z)$ has no higher-order poles for all $i \geq 1$.

	Let us reformulate the second claim:
	\begin{align}
		\label{eq:delta1explicit}
		\delta_1 &= \lim_{z \to \rho_k} \frac{\ell_{k,k-1}(z)}{\frac{\ell_{k,k}(z)}{z-\rho_k}} = \frac{\ell_{k,k-1}(\rho_k)}{\ell'_{k,k}(\rho_k)} = \frac{k}{2},
	\end{align}
	where the second equality sign holds because of de l'Hospital's rule and Lemma~\ref{lem:lkkproperties} ($\rho_k$ is not a root of $\ell_{k,k-1}(z)$). The last equality holds by Lemma~\ref{lem:lkk1}
\end{proof}

With the help of the following lemma, we are able to simplify the indicial polynomials further.
\begin{lemma}
	\label{lem:zeropolys}
	For $k \geq 2$ and $0 \leq i \leq \lfloor \frac{k-2}{2} \rfloor$ we have $\ell_{k,i}(z) \equiv 0$.
\end{lemma}

\begin{proof}
	Let us start with the cases $i=0$ and $i = 1$.
	As defined in Theorem~\ref{theo:Dkprop} we have $\ell_{k,0}(z) = 0$ for $k\geq 2$.  The case $i =1$ is valid for $k \geq 4$. Then, we have
	\begin{align*}
		\ell_{k,1}(z) &= \ell_{k-1,0}(z) - \ell_{k-2,0}(z) = 0.
	\end{align*}

	For the cases $i \geq 2$ we use induction on $k$.
	Assume the claim holds for $2,\ldots,k-1$ and arbitrary $i$. Then, we have
	\begin{align*}
		\ell_{k,i}(z) &= \ell_{k-1,i-1}(z) - (i+1)\ell_{k-2,i-1}(z) - z \ell_{k-2,i-2}(z) =0.
	\end{align*}
	In all three cases it is easy to check that $i \leq \lfloor \frac{k-2}{2} \rfloor$ and the induction hypothesis imply that these terms are equal to $0$.
\end{proof}
Hence, the differential equation of order $k$ is actually a differential equation of order
\begin{alignat*}{5}
	\tilde{r} &:= \left\lceil \frac{k}{2} \right\rceil & \quad \text{ for the function } \quad &
	\tilde{R}_k(z) &:= \frac{d^{\lfloor \frac{k}{2}\rfloor}}{dz^{\lfloor \frac{k}{2}\rfloor}} R_k(z).
\end{alignat*}
In other words, we have
\begin{align}
	\label{eq:relaxedreducedode}
	\ell_{k,k}(z) D^{\tilde{r}} \cdot \tilde{R}_k +
	\ell_{k,k-1}(z) D^{\tilde{r}-1} \cdot \tilde{R}_k + \dots +
	\ell_{k,\lfloor \frac{k}{2}\rfloor}(z) \tilde{R}_k = 0.
\end{align}

\begin{coro}
	\label{coro:indicialpolyreduced}
	Let $\tilde{I}_k(\alpha)$ be the indicial polynomial of the reduced
	differential equation~\eqref{eq:relaxedreducedode}. Then,
	\begin{align*}
		\tilde{I}_k(\alpha) &=
			\begin{cases}
				\alpha^{\underline{\tilde{r}-1}} \left(\alpha+1\right), & \text{if } $k$ \text{ even},\\
				\alpha^{\underline{\tilde{r}-1}} \left(\alpha+\frac{1}{2}\right), & \text{if } $k$ \text{ odd}.
			\end{cases}
	\end{align*}
\end{coro}

\begin{proof}
	This is a direct consequence of Proposition~\ref{prop:indicialpoly}.
	As only the order of the differential equation changed but not its coefficients, we get
	$$\tilde{I}_k(\alpha) = \alpha^{\underline{\tilde{r}}} + \delta_1 \alpha^{\underline{\tilde{r}-1}}
	                      = \alpha^{\underline{\tilde{r}-1}} \left(\alpha - \left\lceil \frac{k}{2} \right\rceil + \frac{k}{2} +  1\right).
	$$
	Considering the even and odd case separately yields the result.
\end{proof}

After these technical steps, we can finally prove our first main result.

\begin{proof}[Proof of Theorem~\ref{theo:relaxededmain}]
	By Lemma~\ref{lem:lkkproperties}, $\rho_k$ is the closest singularity to the origin and unique in the disc of convergence.
	Furthermore, the pole of $\frac{\ell_{k,i}(z)}{\ell_{k,k}(z)}$ at $z=\rho_k$ for $i=1,\ldots,k-1$
	is of order one for $i \geq 1$. Thus, by Definition~\ref{def:regularsing} it is a regular
singularity of the differential equation.

	Furthermore, by Corollary~\ref{coro:indicialpolyreduced} the set of roots of the reduced
indicial polynomial is $\{-1,0,1,\ldots,\tilde{r}-2\}$ for even $k$ and $\{-\frac{1}{2},0,1,\ldots,\tilde{r}-2\}$ for odd $k$.
	In both cases by Theorem~\ref{theo:odeasymptregsing},
	a basis in a slit neighborhood of $\rho_k$ consists of the analytic functions
	\begin{align*}
		(1-z/\rho_k)^s H_s(1-z/\rho_k),
	\end{align*}
	for $s=0,\ldots,\tilde{r}-2$ where $H_s$ is analytic at $0$, and a singular function
	\begin{align*}
		\begin{cases}
			\frac{1}{1-z/\rho_k} H(1-z/\rho_k) + G(1-z/\rho_k) \log(1-z/\rho_k), & \text{ if $k$ is even},\\
			\frac{1}{\sqrt{1-z/\rho_k}} H(1-z/\rho_k), & \text{ if $k$ is odd},\\
		\end{cases}
	\end{align*}
	with functions $G,H$ analytic at $0$. These functions form a basis of the solution space of~\eqref{eq:relaxedreducedode}.

	In order to obtain a basis, we need to integrate $\left\lfloor \frac{k}{2} \right\rfloor$ times.
	The analytic basis functions remain analytic and the singular one singular.
	As there is always just one singular function, and we know that $R_k(z)$ is
	singular at $\rho_k$, this function must be responsible for the asymptotic growth.
	We get a singular expansion for $z \to \rho_k$ of the kind
	\begin{align*}
		R(z) &\sim
				\begin{cases}
					\gamma_k (1-z/\rho_k)^{k/2-1}\log\left(\frac{1}{1-z/\rho_k}\right),  & \text{ if $k$ is even},\\
					\gamma_k (1-z/\rho_k)^{k/2-1},  & \text{ if $k$ is odd}.
				\end{cases}
	\end{align*}
	Finally, applying the transfer theorems~\cite{flaj09}, the claim holds.
\end{proof}

	Let us comment on the even case. It is a priori not clear if this logarithmic term appears or not (if not we set $G\equiv 0$). But due to the appearance of the term with the polar singularity, the logarithmic term does not influence the asymptotic main term. Obviously, it plays a role for the error terms.
	For specific cases, we can of course answer this question. For $k=2$, we have seen in Section~\ref{sec:R2} that there are no logarithmic terms. However, in this case, the reduced indicial polynomial is only of order $1$, see Corollary~\ref{coro:indicialpolyreduced}. Therefore, the consecutive range of roots starting with $0$ does not exist.

	For $k=4$, logarithmic terms appear. In this case we have the operator
	\begin{align*}
		(-z^3+6 z^2-5 z+1)D^2+(-6 z^2+24 z-10)D+(11-6 z)
	\end{align*}
	and the expansion point $\rho_4$ that is a root of $-z^3+6 z^2-5 z+1$.
	Then, the solution space is generated by the following two series:

\def\LandauO{\mathcal{O}}

\begin{tabular}{l l}
$1$ & \phantom{$+\tfrac{3255\rho_4^2-175989 \rho_4+805466}{49392} (\rho_4-z)^3 \log (z-\rho_4)$} \\
$-\tfrac{48 \rho_4^2-267 \rho_4+118}{14} (\rho_4-z)$ & \\
$+\tfrac{249 \rho_4^2-2340 \rho_4+5560}{588} (\rho_4-z)^2$ & \\
$-\tfrac{206442 \rho_4^2-1141941 \rho_4+502699}{7056} (\rho_4-z)^3$ & \\
$+\LandauO((\rho_4-z)^{4}),$ &
\end{tabular}

\medskip
and \\
\smallskip

\begin{tabular}{l l}
$(z-\rho_4)^{-1}$ & $+0\,(z-\rho_4)^{-1}\log(z-\rho_4)$ \\
$+0$ & $-\tfrac{6 \rho_4^2-33 \rho_4+14}{7} \log(z-\rho_4)$ \\
$+\tfrac{159 \rho_4^2-888 \rho_4+440}{196} (\rho_4-z)$ & $+\tfrac{3 \rho_4^2-54 \rho_4+194}{98} (\rho_4-z) \log (z-\rho_4)$ \\
$-\tfrac{2484 \rho_4^2-14439 \rho_4+9541}{1764} (\rho_4-z)^2$ & $-\tfrac{3834 \rho_4^2-21183 \rho_4+9221}{588} (\rho_4-z)^2 \log(z-\rho_4)$ \\
$+\tfrac{4199487 \rho_4^2-23629269 \rho_4+12255158}{592704} (\rho_4-z)^3$ & $+\tfrac{3255\rho_4^2-175989 \rho_4+805466}{49392} (\rho_4-z)^3 \log (z-\rho_4)$ \\
$+\LandauO((\rho_4-z)^{4}\log(z-\rho_4)).$ &
\end{tabular}

\section{Compacted binary trees}
\label{sec:compacted}

After the successful application of exponential generating functions
to relaxed trees of bounded right height, we will extend this method to compacted binary trees.
In this section we solve the problem of finding the generating function of compacted trees of bounded right height. We denote the class of compacted trees of right height at most $k$ by $\mathcal{C}_k$ and its corresponding exponential generating function by $C_k(z) = \sum_{n \geq 0} c_{k,n} \frac{z^n}{n!}$.

As every subtree in a relaxed tree of right height at most $0$ is unique, by Corollary~\ref{coro:R0} we immediately get
\[
	C_0(z) = \frac{1}{1-z}.
\]

\subsection{The cherry operator}
\label{sec:C1}

We start with the subclass $\mathcal{C}_1$ of compacted trees of right height at most $1$.
The same ideas as in Section~\ref{sec:R1} are used in the analysis.
However, this case is more subtle as we have to guarantee uniqueness of the subtrees.
The main observation in this context is that in order to establish uniqueness
of the subtrees one needs to restrict the pointers of the cherries, see Proposition~\ref{prop:characterizingcompactedtrees}.

Consider a situation where the pointers of a cherry are pointing into a tree of size $k$.
Thus,  every pointer has $k+1$ possibilities ($+1$ due to the leaf).
In a relaxed setting this would mean that there are $(k+1)^2$ different configurations.

In a compacted tree every internal node (or spine node) corresponds to a unique subtree.
Therefore, the cherry has only $(k+1)^2-k$ different options, see also Theorem~\ref{theo:comprecursion}. Let us introduce the corresponding operator now.

\begin{lemma}[Cherry operator]
	Let $\mathcal{C}$ be a class of compacted trees and $\mathcal{K}$ be the class obtained from $\mathcal{C}$
	by adding a new node with two pointers, where the decompacted tree of this new node
	(left pointer is left child, right pointer is right child) is not part of $\mathcal{C}$.  Then,
	\begin{align*}
		K(z) &= z \left(zC(z)\right)' - \int z C'(z) \, dz \\
			  &= z^2 C'(z) + \int C(z) \, dz.
	\end{align*}
\end{lemma}

\begin{proof}
	The first term corresponds to the (unconstrained) operation of adding a root with two pointers, see~\eqref{eq:addrootwith2pointers}. The second one is responsible for the correction, by deleting the number of subtrees which are already part of $\mathcal{C}$, see Figure~\ref{fig:cherryoperator}:

	Consider a tree of $\mathcal{C}$ of size $k$. The integrand creates a pointer attached to the root possibly pointing to all elements of the subtree. The integration operator adds a new root node without a pointer. By attaching the newly created pointer to this new root, and changing the pointer in the case of it pointing to the leaf by letting it point to the old root, we generate $k$ new elements from this specific tree: A new root with a pointer to every internal node of the tree.
	This is exactly the number of elements which we need to subtract in order to ensure uniqueness.

	The second expression results from an integration by parts of the first one.
\end{proof}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.8\textwidth]{cherryoperator}
	\caption{\small The construction of the cherry operator. The formulas below the pointers state the possible destinations of the pointers in the tree $\mathcal{T}_k$. The left tree is the desired one, the other ones are constructible ones. }
	\label{fig:cherryoperator}
\end{figure}

Let us also define the corresponding operator which performs the previous operation:
\begin{align*}
	K(C(z)) := z \left(zC(z)\right)' - \int z C'(z) \, dz.
\end{align*}

Next, we decompose $\mathcal{C}_1$ into
\begin{align*}
	C_1(z) &= \sum_{\ell \geq 0} C_{1,\ell}(z),
\end{align*}
where $C_{1,\ell}(z)$ is the exponential generating function of compacted trees of right height at most $1$ with exactly $\ell$ right edges in the spine going from level $0$ to level $1$.

\begin{coro}
	\label{coro:C1l}
	The generating function of compacted trees with exactly $\ell$ right edges from level $0$ to level $1$ in the spine is given by
	\begin{align*}
		C_{1,\ell}(z) &= \frac{1}{1-z} \int \frac{1}{1-z} K\left( C_{1,\ell-1}(z) \right) \, dz , \qquad \ell \geq 1,\\
		C_{1,0}(z) &= \frac{1}{1-z}.
	\end{align*}
\end{coro}

\begin{proof}
	The construction is analogous to the one of Corollary~\ref{coro:R1l}.
	The only difference is the use of the cherry operator in~\eqref{eq:addrootwith2pointers}.
\end{proof}

\begin{theo}
	\label{theo:C1}
	The exponential generating function of compacted trees of right height at most~$1$ is D-finite and satisfies
	\begin{align*}
		(1-2z) C_1''(z) - (3-z)C_1'(z) &= 0, &
		C_1(0)=1, \quad
		C'_1(0)=1.
	\end{align*}
	The closed form formula for $C_1'(z)$, and the asymptotic behavior of the coefficients are given by
	\begin{align*}
		C_1'(z) &= \frac{e^{z/2}}{(1-2z)^{5/4}}, &
		c_{1,n} &= \frac{e^{1/4}}{\Gamma(1/4)} \frac{ n! 2^{n+1}}{ n^{3/4} } \left( 1 + \mathcal{O}\left(\frac{1}{n} \right) \right).
	\end{align*}
\end{theo}

\begin{proof}
	Summing the result of Corollary~\ref{coro:C1l} for $l \geq 1$, interchanging summation, differentiation, and finally integration gives
	\begin{align*}
		(1-2z) C_1'(z) - C_1(z) - (1-z) \left( (1-z) C_{1,0} \right)' + \int z C_1'(z) \, dz = 0.
	\end{align*}
	Due to the remaining integral we differentiate both sides once more and get
	\begin{align}
		(1-2z) C_1''(z) - (3-z)C_1'(z) - \left((1-z) \left( (1-z) C_{1,0} \right)' \right)' = 0. \label{eq:C1dfinite}
	\end{align}
	Inserting $C_{1,0}(z) = C_0(z) = \frac{1}{1-z}$ we get the claimed differential equation
	\begin{align*}
		(1-2z) C_1''(z) - (3-z)C_1'(z) &= 0
	\end{align*}
	It can be solved by separation of variables with respect to $C_1'(z)$.
	The asymptotic behavior of the coefficients follows then directly from this representation.
\end{proof}

\subsection{Compacted trees of right height at most 2}
\label{sec:C2}

We decompose $\mathcal{C}_2$ such that we get
\begin{align*}
	C_2(z) &= \sum_{\ell \geq 0} C_{2,\ell}(z),
\end{align*}
where $C_{2,\ell}(z)$ is the exponential generating function of compacted trees of right height at most $2$ with exactly $\ell$ right edges in the spine going from level $0$ to level $1$.  Obviously, we have $C_{2,0}(z) = \frac{1}{1-z}$.

In the sequel we will use the operator calculus introduced in Section~\ref{sec:operations}.

\begin{prop}
	\label{prop:C2l}
	The generating function of compacted trees with right height at most $2$, and exactly $\ell$ right edges from level $0$ to level $1$ in the spine is given by
	\begin{align*}
		C_{2,\ell}(z) &= C_{2,\ell,A}(z) + C_{2,\ell,B}(z),\\
		C_{2,\ell,A}(z) &= A(C_{2,\ell-1}(z)),\\
		\bar{D}_2(C_{2,\ell,B}(z)) &= \bar{H}_2({C}_{2,\ell-1}(z)),
	\end{align*}
	with the linear operators $A = S \cdot I \cdot S \cdot K$, $\bar{D}_2 = M_1 \cdot D \cdot S^{-1}$, $\bar{H}_2 = (H_1 - M_1) \cdot (D\cdot z + S \cdot K)$, and $M_1$ and $H_1$ are given by
	\begin{align}
			M_1 &= (1-2z) D^2 - (3-z) D, \label{eq:compM1}\\
			H_1 &= (1-z)^2 D^2 - 3(1-z) D + 1. \label{eq:compH1}
	\end{align}
\end{prop}

\begin{proof}
Using the same ideas as in the case of relaxed trees, we reduce
the number of levels by deleting the initial sequence,
and moving the last sequence to the end of the next lower level, see Figure~\ref{fig:R21decomp}.
This produces a $\mathcal{C}_1$-like object with
\begin{itemize}
	\item a new initial condition $\hat{C}_{2,0}(z)$ and
	\item the restriction of being non-empty.
\end{itemize}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.33\textwidth]{C2A}
	\qquad
	\includegraphics[width=0.4\textwidth]{C2B}
	\caption{\small The $2$ possible cases for $\mathcal{C}_{2}$ instances:
		Case (A) on the left, where level $2$ does not exist;
		and case (B) on the right, where level $2$ does exist.}
	\label{fig:C2AB}
\end{figure}

In contrast to the relaxed case of $\mathcal{R}_{2,1}$ we need to distinguish whether level $2$ exists or not
(Figure~\ref{fig:C2AB}). The different behaviors of single pointers and (double)
cherry pointers are responsible for these two cases. Let $C_{2,1} \in \mathcal{C}_{2,1}$,
$\hat{C}_{2,0}$ be the transformed object and $C_{2,0}$ be the part of level~$0$ located after the first right edge on level $0$ ($\mathcal{T}$ in Figure~\ref{fig:C2AB}).

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.4\textwidth]{C20hat}
	\caption{\small The new initial condition $\hat{C}_{2,0}(z)$. In case (A) the last sequence on level~$1$ cannot be empty, whereas in case (B) it may.}
	\label{fig:C20hat}
\end{figure}

\begin{enumerate}
	\item[(A)]
		Let $C_{2,1,A}(z)$ be the generating function of compacted trees belonging to Case (A) and $\mathcal{C}_{2,1}$.
		In this case level $2$ does not exist
		(i.e.~the tree also belongs to $\mathcal{C}_{1}$). Then we need to have a cherry on level $1$,
		as this level is not allowed to be empty. This implies that the sequence
		of $\hat{C}_{2,0}$ shown in Figure~\ref{fig:C20hat} cannot be empty.
		Then, due to the previous reasoning on relaxed trees (cf. Proposition~\ref{prop:R11}),
		and results on the trees in $\mathcal{C}_{1}$ (Corollary~\ref{coro:C1l}), we get the new initial condition for Case~(A): Instead of $C_{1,0}(z)$ in~\eqref{eq:C1dfinite} we must use
		\begin{align*}
			\hat{C}_{2,0,A}(z)
				&:= \frac{1}{1-z}  K\left( C_{2,0}(z) \right)
				 = \frac{z\left( z C_{2,0}(z)\right)' - \int z C_{2,0}'(z) \, dz}{1-z}.
		\end{align*}
		This implies
		\begin{align*}
			C_{2,1,A}(z) &= A(C_{2,0,A}(z)) := \frac{1}{1-z} \int \hat{C}_{2,0,A}(z) \, dz = \frac{1}{1-z} \int \frac{1}{1-z} K \left( C_{2,0,A}(z) \right) \, dz.
		\end{align*}
		The first factor $\frac{1}{1-z}$ corresponds to the initial sequence on level $0$, and the integral generates the level $0$ node of the distinguished right edge. In anticipation of the subsequent result, we introduced the operator $A$.

	\item[(B)]
		Let $C_{2,1,B}(z)$ be the generating function of this case.
		In this case level $2$ exists.
		Then the last sequence of level $1$, and therefore the initial sequence of $\hat{C}_{2,0}$, is allowed to be empty, see Figure~\ref{fig:C20hat}.
		This means that no cherry was lost during the transformation into an instance of $\mathcal{C}_{1}$
		as there is just one pointer pointing into $C_{2,0}$.
		Such a case is modeled by $(z C_{2,0}(z))'$.
		Combining it with the case of a non-empty sequence, we get the new initial condition of the case~(B):
		\begin{align*}
			\hat{C}_{2,0,B}(z)
				&:= \left(z C_{2,0}(z) \right)' + \frac{1}{1-z} K\left( C_{2,0}(z) \right)
				 = \frac{ \left(z C_{2,0}(z)\right)' - \int z C_{2,0}'(z) \, dz}{1-z}.
		\end{align*}

		The only difference to case (A) is the lack of the factor $z$ in front of $\left(z C_{2,0}(z)\right)'$.

		By assumption we have nodes on the level $2$.
		This means that after the transformation into an instance of $\mathcal{C}_{1}$
		 we have nodes on level $1$. Let $\bar{C}_1(z)$ be the exponential generating function
		of compacted trees of right height at most $1$ with at least one node on level~$1$. Then
		\begin{align*}
			\bar{C}_1(z) &= \sum_{\ell \geq 1} C_{1,\ell}(z) = C_{1}(z) - C_{1,0}(z).
		\end{align*}
		The new operators, defined in \eqref{eq:compM1} and \eqref{eq:compH1}, fulfill the same tasks as the ones from Theorem~\ref{theo:diffoprelaxed} for relaxed trees.
		From~\eqref{eq:C1dfinite} we infer that $C_{1}(z)$ satisfies $M_1(C_1(z)) = H_1(C_{0}(z))$. Thus, for $\bar{C}_1(z)$ we get the following differential equation:
		\begin{align*}
			M_1(\bar{C}_1(z)) = M_1(C_1(z) - C_{1,0}(z)) = H_1(C_{1,0}(z)) - M_1( C_{1,0}(z))
			.
		\end{align*}
		Then, the differential equation for $C_{2,1,B}(z)$ is given by
		\begin{align*}
			\bar{D}_2(C_{2,1,B}(z)) &:= M_1 \left( \left((1-z) C_{2,1,B}(z)\right)'\right) \\
			                           &= H_1(\hat{C}_{2,0,B}(z)) - M_1( \hat{C}_{2,0,B}(z) )
												 =: \bar{H}_2({C}_{2,0}(z)),
		\end{align*}
		because we are able to reuse~\eqref{eq:C1dfinite}, with the new initial condition $\hat{C}_{2,0,B}(z)$ instead of $C_{1,0}(z)$. Its solution is equal to $\left((1-z) C_{2,1,B}(z)\right)'$;
		see the process of Proposition~\ref{prop:R21}.
		The new differential operator is thus given by
		\begin{align*}
			\bar{D}_2(F) = (2z^2-3z+1) F''' - (z^2-10z+6)F'' - (2z-6) F'.
		\end{align*}
\end{enumerate}

This process can now be continued recursively, like in Corollary~\ref{coro:R2l}.
In order to derive $C_{2,2}(z)$, we replace $C_{2,0}(z)$ by $C_{2,1}(z)$, and so on.
\end{proof}

Using the last result we are able to characterize compacted trees of right height at most~$2$.

\begin{theo}
	\label{theo:C2}
	The exponential generating function of compacted trees of right height at most~$2$ is D-finite and satisfies
	\begin{align*}
		(z^2-3z+1) C_2'''(z) - (z^2-6z+6) C_2''(z) - (2z-3) C_2'(z) &= 0, \\
		C_2(0)=1,~C_2'(0)=1,~C_2''(0)&=3.
	\end{align*}
\end{theo}

\begin{proof}
	The generating function $C_2(z)$ is decomposed into three parts:
	\begin{align*}
		C_{2}(z) &= C_{2,0}(z) + C_{2,A}(z) + C_{2,B}(z),
	\end{align*}
	where $C_{2,A}(z) = \sum_{\ell \geq 0} C_{2,\ell, A}(z)$, $C_{2,B}(z) = \sum_{\ell \geq 0} C_{2,\ell, B}(z)$, and the initial values $C_{2,0,A}(z) = C_{2,0,B}(z) = 0$.
	%
	Summing the results of Proposition~\ref{prop:C2l} for $\ell \geq 1$ gives
	\begin{align*}
		C_{2,A}(z) &= A(C_{2}(z)),\\
		\bar{D}_2(C_{2,B}(z)) &= \bar{H}_2({C}_{2}(z)).
	\end{align*}
	Finally, we get
	\begin{align*}
		\bar{D}_2(C_{2}) &= \bar{D}_2(C_{2,0} + C_{2,A} + C_{2,B}) \\
		                       &= \bar{D}_2(C_{2,0}) + \bar{D}_2(A(C_{2})) + \bar{H}_2({C}_{2}),
	\end{align*}
	which gives the new differential operator $M_{2}$ and the inhomogeneity operator $H_2$:
	\begin{align}
		\label{eq:compM2operators}
		M_2(C_{2}) := \bar{D}_2(C_{2}) - \bar{D}_2(A(C_{2})) - \bar{H}_2({C}_{2}) = \bar{D}_2(C_{2,0}) =: H_2(C_{2,0}).
	\end{align}
	Note that in analogy to~\eqref{eq:relLHk}  from the relaxed case we have here
	\begin{align*}
		H_{2}  = M_1 \cdot D \cdot (1-z).
	\end{align*}
	The computation of $M_2$ is direct with a computer algebra system (like Maple or Sage).
\end{proof}

\subsection{Compacted trees of right height at most \texorpdfstring{$k$}{k}}

Analogous to the case of relaxed trees in Section~\ref{sec:relaxedheightk} the approach from the previous section can be generalized to an arbitrary bound $k \geq 2$ for the right height.

We introduce linear differential operators $M_k$, $k \geq 0$ which describe all differential equations
constructed for $C_k(z)$. We use the same notation as in Section~\ref{sec:relaxedheightk}.
\begin{theo}[Differential operators]
	\label{theo:diffopcompacted}
	Let $(M_k)_{k \geq 0}$ be the family of differential operators given by
	\begin{align*}
		M_0 &= (1-z) D - 1,\\
		M_1 &= (1-2z) D^2 - (3-z)D, \\
		M_{k} &= M_{k-1} \cdot D - M_{k-2} \cdot \left( D^2 \cdot z - z D\right), \qquad k \geq 2.
	\end{align*}
	Then the exponential generating function $C_k(z)$ of compacted binary trees with right height at most $k$ satisfies
	\begin{align*}
		M_k \cdot C_k &= 0.
	\end{align*}
\end{theo}

\begin{proof}
	The ideas are the same as the ones introduced in the proof of Theorem~\ref{theo:diffoprelaxed}:
	In an instance of $\mathcal{C}_k$ we cut at the first right edge in the spine from level $0$ to level $1$.
	Then, the same decomposition as in the case $k=2$ can be applied (like in Figure~\ref{fig:R21decomp}).

	In particular, first generalizing the results of Propositition~\ref{prop:C2l} we get
	\begin{align*}
		\bar{D}_k &= M_{k-1} \cdot D \cdot S^{-1} \\
		\bar{H}_k &= \left( \bar{D}_{k-1} - M_{k-1} \right) (D \cdot z + S \cdot K ),
	\end{align*}
	which together with~\eqref{eq:compM2operators} implies on the level of operators
	\begin{align*}
		M_{k} &= \bar{D}_k - \bar{D}_k \cdot A - \bar{H}_k \\
				  &= M_{k-1} \cdot D - M_{k-2} \cdot \left(D^2 z - z D\right).
	\end{align*}
	Recall for the second equality that $S$ and $I$ are inverse to each other, and
	that $S^{-1} = (1-z)$, and $K = zDz - IzD$.
\end{proof}

The first few differential equations are
\begin{equation*}
	(1-2z) \frac{d^2}{dz^2} C_1(z) + (z-3) \frac{d}{dz}C_1(z) = 0,
\end{equation*}
\begin{equation*}
	(z^2 - 3z + 1) \frac{d^{3}}{dz^{3}} C_2(z) - (z^2-6z+6) \frac{d^2}{dz^2} C_2(z) - (2z-3) \frac{d}{dz} C_2(z) = 0,
\end{equation*}
\begin{equation*}
	(3z^2-4z+1) \frac{d^{4}}{dz^{4}} C_3(z) - (4z^2-18z+10) \frac{d^{3}}{dz^{3}} C_3(z) + (z^2-12z+14) \frac{d^{2}}{dz^{2}}C_3(z) + (z-3) \frac{d}{dz} C_3(z) = 0.
\end{equation*}

\begin{theo}[Properties of $M_k$]
	\label{theo:Ekprop}
	The operator $M_k$ is a linear differential operator of order~$k+1$ satisfying
	\begin{align*}
		M_k &= m_{k,k}(z) D^{k+1}
						+ m_{k,k-1}(z) D^{k}
						+ \ldots
						+ m_{k,0}(z) D
						+ m_{k,-1}(z) ,
	\end{align*}
	where the $m_{k,i}(z)$ are polynomials given by the following recurrence relation for $k \geq 2$
	\begin{align*}
		m_{k,-1}(z) &= 0,\\
		m_{k,0}(z) &=
			\begin{cases}
				-2z+3, & \text{ for $k$ even,}\\
				z-3, & \text{ for $k$ odd,}
			\end{cases}\\
		m_{k,i}(z) &= m_{k-1,i-1}(z) + (i+1) m_{k-2,i}(z) \\
		           &\qquad + (z-i-2) m_{k-2,i-1}(z) - z m_{k-2,i-2}(z), \qquad 1 \leq i \leq k-1,\\
		m_{k,k}(z) &= m_{k-1,k-1}(z) - z m_{k-2,k-2}(z), \\
		m_{k,i}(z) &= 0, \qquad i > k.
	\end{align*}
	The initial polynomials are $m_{0,-1}(z) = -1$, $m_{0,0} = 1-z$, $m_{1,-1}=0$, $m_{1,0}=z-3$, and $m_{1,1}(z) = 1-2z$. The leading coefficients $m_{k,k}(z)$ are the same as $\ell_{k,k}(z)$ from the relaxed case.
\end{theo}

\begin{proof}
	The proof is analogous to the one of Theorem~\ref{theo:Dkprop}. We omit the tedious calculations.
\end{proof}

It may seem artificial to start the second index at $-1$. However, the corresponding polynomials are equal to $0$ except when $k=0$. Thus, we are actually dealing with a differential equation of order $k$ in $F'(z)$. Another advantage is that the leading polynomial $m_{k,k}(z)$, which is the same as the one in the relaxed case $\ell_{k,k}(z)$, has the same indices.

Following the approach used for relaxed trees,
we then need to reveal the structure of the indicial polynomial.

In order to compute the value $\delta_1 = \lim_{z \to \zeta}(z-\zeta)a_1(z)$
(compare with~\eqref{eq:difeqmerogen}),
we need the following result on $m_{k,k-1}(z)$.

\begin{lemma}[Transformed $m_{k,k-1}(z)$]
	\label{lem:chebyshevmkk1}
	For the coefficient $m_{k,k-1}(z)$ of the operator $M_k$ from Theorem~\ref{theo:Ekprop},
	we get
	\begin{align*}
		m_{k,k-1}(z) &= z^{\frac{k+2}{2}} h_{k+2}\left(\frac{1}{2 \sqrt{z}}\right),
	\end{align*}
	where
	\begin{align*}
		h_k(z) &= \frac{\left(k-3 - 2(k^2+k-2)z^2\right) T_k(z) + \left( 1 + 2(k-1)z^2 \right) U_k(z)}{2(z^2-1)},
	\end{align*}
	and $T_k(z)$ and $U_k(z)$ are the Chebyshev polynomials of first and second kind, respectively.
\end{lemma}

\begin{proof}
		From Theorem~\ref{theo:Ekprop} we get the recurrence relation of $m_{k,k-1}(z)$:
		\begin{align*}
			m_{k,k-1}(z) = m_{k-1,k-2}(z) - z m_{k-2,k-3}(z) + (z-k-1)m_{k-2,k-2}(z).
		\end{align*}
		Its structure is similar to the one of $m_{k,k}(z)$, but with an additional perturbation $(z-k-1)m_{k-2,k-2}(z)$. Transforming it in the same way as the one of $m_{k,k}(z)$ we get with
		$$
			h_{k+2}(z) := (2z)^{k+2} m_{k,k-1}\left(\frac{1}{4z^2}\right),
		$$
		for $k \geq 0$ the recurrence
		\begin{align*}
			h_{k+2}(z) = 2z h_{k+1}(z) - h_{k}(z) + \left(1 - 4z^2 (k+1) \right) U_{k}(z).
		\end{align*}
		From the theory of recurrences with constant coefficients (with respect to $k$) \cite[Chapter~$4$]{KauersPaule11} we get that the solution space is generated by
		$
			U_k(z),
			T_k(z),
			k U_k(z),
			k T_k(z),
			k^2 U_k(z),
			k^2 T_k(z).
		$
		Making an ansatz and comparing coefficients gives the result.
\end{proof}

\begin{prop}
	\label{prop:indicialpolycompacted}
	Let $I_k(\alpha) = \alpha^{\underline{k+1}} + \delta_1 \alpha^{\underline{k}} + \cdots + \delta_{k+1}$ be the indicial polynomial  of the $k$-th differential equation, and let $\rho_k$ be the smallest real root of $m_{k,k}(z)$. Then, we have $\delta_i = 0$ for $i > 1$, and $\delta_1 = \frac{m_{k,k-1}(\rho_k)}{m'_{k,k}(\rho_k)}$. Furthermore, we have
	\begin{align*}
		\delta_1 &= \frac{k}{2} + 1 - \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\frac{1}{\cos^2\left(\frac{\pi}{k+3}\right)}.
		\end{align*}
	The indicial polynomial is given by $I_k(\alpha) = \alpha^{\underline{k}} (\alpha-(k-\delta_1))$.
\end{prop}

\begin{proof}
	The first results are analogous to the ones in Proposition~\ref{prop:indicialpoly}: First, because of Lemma~\ref{lem:lkkproperties} we have $\delta_i=0$ for $i > 0$. Second, the expression for $\delta_1$ is the same
	as~\eqref{eq:delta1explicit}, and follows from de l'Hospital's rule.
	Thus, the indicial polynomial is given by $I_k(\alpha) = \alpha^{\underline{k+1}} + \delta_1\alpha^{\underline{k}}$.

	We start with two simplifications for the root $x_k = \cos(\frac{\pi}{k+1})$ of $U_k(z)$ when inserted into $T_k(z)$. By the explicit expression
	$
		T_k(x) = \cos \left( k \arccos(x)\right), \text{ for } |x| \leq 1,
	$
	we get
	\begin{align*}
		T_{k}(x_{k}) &= - \cos\left(\frac{\pi}{k+1} \right) = - x_{k}, && \text{ and } &
		T_{k+1}(x_{k}) &= -1.
	\end{align*}

	First, we consider $m_{k,k-1}(z)$. By Lemma~\ref{lem:chebyshevmkk1} we directly get
	\begin{align*}
		m_{k,k-1}(\rho_k) &= \rho_{k}^{\frac{k+2}{2}} \frac{(k-1)x_{k+2} - 2((k+2)^2+k) x_{k+2}^3}{2 (x_{k+2}^2-1)},
	\end{align*}
	where $\rho_k = \frac{1}{4x_{k+2}^2}$, and recall that $U_{k}(x_k) = 0$.

	Second, we consider the derivative of $m_{k,k}(z)$. Therefore, we use the following connection between Chebyshev polynomials of the first and second kind, see~\cite[Section~18.9]{NIST:DLMF}:
	\begin{align*}
		U'_k(z) = \frac{(k+1) T_{k+1}(z) - z U_k(z)}{z^2-1}.
	\end{align*}
	Thus, by Lemma~\ref{lem:chebyshev} we get
	\begin{align*}
		m'_{k,k}(\rho_k) &= \frac{\rho_k^{\frac{k-1}{2}}}{4} \frac{k+3}{x_{k+2}^2-1}.
	\end{align*}
	Combining these results shows the claim.
\end{proof}

We arrive at our main result for compacted binary trees, Theorem~\ref{theo:compactedmain}.

\begin{proof}[Proof of Theorem~\ref{theo:compactedmain}]
	The proof follows the same lines as the one of Theorem~\ref{theo:relaxededmain}. In particular, the third case of Theorem~\ref{theo:odeasymptregsing} gives the asymptotic result, as $\delta_1$ is irrational for all $k \in \mathbb{N}$.
\end{proof}

In contrast to relaxed trees, the asymptotics of compacted trees involves in general an irrational critical exponent. In Table~\ref{tab:compcritexp} we list their first explicit values.

\begin{table}[ht]
	\begin{center}
	\begin{tabular}{|c||c|c||c|c||c|c|}
		\hline $k$      & $r$ & $r \approx$ & $\alpha$ & $\alpha \approx$ & $\beta$ & $\beta \approx$ \\
		\hline\hline
		$1$ & $2$ & $2.000$ & $-\frac{3}{4}$ & $-0.750$ & $-\frac{1}{2}$ & $-0.5$ \\
		$2$ & $4 \cos(\frac{\pi}{5})^2$ & $2.618$ & $-\frac{6}{5}-\frac{1}{20\cos(\frac{\pi}{5})^2}$ & $-1.276$ & $-1$ & $-1.0$ \\
		$3$ & $3$ & $3.000$ & $-\frac{16}{9}$ & $-1.778$ & $-\frac{3}{2}$ & $-1.5$ \\
		$4$ & $4 \cos(\frac{\pi}{7})^2$ & $3.246$ & $-\frac{15}{7}-\frac{3}{28\cos(\frac{\pi}{7})^2}$ & $-2.275$ & $-2$ & $-2.0$ \\
		$5$ & $4 \cos(\frac{\pi}{8})^2$ & $3.414$ & $-\frac{21}{8}-\frac{1}{8\cos(\frac{\pi}{8})^2}$ & $-2.772$  & $-\frac{5}{2}$ & $-2.5$ \\
		$6$ & $4 \cos(\frac{\pi}{9})^2$ & $3.532$ & $-\frac{28}{9}-\frac{5}{36\cos(\frac{\pi}{9})^2}$ & $-3.268$ & $-3$ & $-3.0$ \\
		$7$ & $4 \cos(\frac{\pi}{10})^2$ & $3.618$ & $-\frac{18}{5}-\frac{3}{20\cos(\frac{\pi}{10})^2}$ & $-3.766$  & $-\frac{7}{2}$ & $-3.5$ \\
		\hline
  \end{tabular}
\end{center}
\caption{\small The number $c_{k,n}$ ($r_{k,n}$) of compacted trees (respectively relaxed trees)
	with $n$ internal nodes and right height at most $k$ is asymptotically equal to $\kappa_k n! r^{n} n^{\alpha}$
	(resp. $\gamma_k n! r^{n} n^{\beta}$) with $r = \rho_k^{-1}$.
}
\label{tab:compcritexp}
\end{table}

\section{Conclusion}
\label{sec:conclusion}

In this paper we solved the asymptotic counting problem for compacted and relaxed binary trees of bounded right height. In a compacted binary tree repeatedly occurring subtrees have been deleted and replaced by pointers to the first appearance, and hence every subtree is unique. By doing so, the tree structure is destroyed and replaced by a directed acyclic graph. In a relaxed binary tree the uniqueness condition of subtrees is omitted.

The difficulty of this counting problem is founded in the compaction procedure. A compacted binary tree of size $n$, where the size is the number of internal nodes, arises from a binary tree whose size is between $n$ and $2^n$.
Our main results with regard to the general counting problem, are recurrence relations for compacted and relaxed binary trees in Theorem~\ref{theo:comprecursion} and Corollary~\ref{coro:relaxedrecurrence}, respectively.

Due to their superexponential growth of order $\Theta(n! \rho_k^{-n} n^{\alpha_k})$ with $\rho_k \approx 1/4$, exponential generating functions are the natural choice. Our second main contribution is the development of a calculus on such exponential generating functions modeling the structural properties of compacted trees in Section~\ref{sec:operations}.

Resulting from these ideas, we were able to give our last main result: the derivation of ordinary differential equations for relaxed and compacted binary trees of bounded right height. The right height of a tree is the maximal number of right edges from the root to any leaf. Furthermore, we extracted the asymptotics by extending the theory of coefficient extractions of ordinary differential equations with polynomial coefficients in Theorem~\ref{theo:odeasymptregsing}. This yielded the sought asymptotics in Theorems~\ref{theo:relaxededmain} and \ref{theo:compactedmain}.

Thereby we discovered quite \emph{exotic} families of enriched trees. The radii of convergence are in both cases algebraic numbers, and in the case of compacted trees, also the critical exponents are (compare Table~\ref{tab:compcritexp} for the first $7$ families).

It remains an open problem to find the asymptotics of relaxed and compacted trees without any restrictions. For our methods it was crucial that the right height was bounded by a fixed value $k$. The limit $k \to \infty$ is therefore not computable. Note that we showed that the radius of convergence $\rho_k$ converges to $1/4$. But the subexponential growth is of the shape $n^{- \lambda k}$ for $\lambda>0$. Thus, it would converge to $0$. Hence, the limits $n\to \infty$ and $k \to \infty$ are not interchangeable.

Finally, it is interesting to compare the number of compacted trees to the number of relaxed trees
in Corollary~\ref{coro:compamongrelaxed}. We showed that their number is negligible for large $n$
and derived a precise quantitative result as well.

Many new questions arise after our analysis. It would be interesting to consider parameters such as their average height or average right height. Furthermore, these results gave us generating functions of a large family of DAGs which should allow a uniform random generation of such trees. Such results are interesting in computer science and the analysis of algorithms, as DAGs are efficient data structures and widely-used. Among other things, new algorithms need to be tested on very large and non-trivial elements of an efficiently computable class of DAGs.

\addcontentsline{toc}{section}{Acknowledgments}
\section*{Acknowledgments}
\label{sec:ack}
We would like to thank Christian Krattenthaler for pointing out the connection with the Chebyshev polynomials.

\addcontentsline{toc}{section}{References}
\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv