The number of monotone full binary trees

Question

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each equivalence class.

I have described the $\mathscr{L}$-cross-sections of the finite full symmetric semigroup $\mathscr{T}_n$, for Green's relation $\mathscr{L}$. Now I try to count them. It turned out that the number of different $\mathscr{L}$-cross-sections is the number of monotone full binary trees (the necessary definitions see below).

Let $X$ be a nonempty finite set and let $<$ be a strict total order on X. We define a strict order $\prec$ on the family of nonempty subsets of $X$ by: $A\prec B$ if for all $a\in A$ and all $b\in B$, $a < b$.

Denote by $\{1,2\}^{+}$ the free semigroup of words over the alphabet $\{1,2\}$, and by $\{1,2\}^{*}$ the free monoid over $\{1,2\}$, with 0 as the empty word.

Let $X$ be a finite set (possibly empty) and let $<$ be a strict total order on $X$. An indexed family $\{A_a\}_{a\in\{1,2\}^{*}}$ of subsets of $X$ is called a $\Gamma$-family over $(X,<)$ if for every $a\in\{1,2\}^{*}$:

(a) $A_0 = X$;

(b) if $|A_a|\leq 1$, then $A_{a1} = A_{a2} = \varnothing$;

(c) if $|A_a|> 1$, then $A_{a1}$ and $A_{a2}$ are nonempty with $A_{a1}\prec A_{a2}$, $A_a=A_{a1}\cup A_{a2}$.

We will say that $\{A_a\}_{a\in\{1,2\}^{*}}$ is a $\Gamma$-family over $X$ if $\{A_a\}_{a\in\{1,2\}^{*}}$ is a $\Gamma$-family over $(X,<)$ for some strict total order $<$ on $X$ (necessarily unique). For simplicity, we will write $\Gamma= \{A_a\}$ instead of $\Gamma= \{A_a\}_{a\in\{1,2\}^{*}}$.

Recall that a binary tree consists of a finite set of nodes that is either empty, or consists of one specially designated node called the root of the binary tree. A full binary tree is a tree in which every node other than the leaves has two children.

It is easy to see, that every $\Gamma$-family $\Gamma= \{A_a\}$ over a nonempty set can be represented by a rooted full binary tree $T(\Gamma)$ whose vertices are nonempty sets from $\{A_{a}\}$ and a pair $\{A_a,A_b\}$, for $a,b\in\{1,2\}^*$, is an edge if and only if $a=bi$ or $b=ai$, where $i=1,2$ (see, https://cloud.mail.ru/public/cdd1f27773a8/An%20arbitrary%20full%20binary%20tree.gif). For the full binary tree, which represents a $\Gamma$-family, we will write further just $\Gamma$ instead of $T(\Gamma)$.

Let $\Gamma= \{A_a\}_{a\in\{1,2\}^*}$ be an $\Gamma$-family over $X$. For every $a\in\{1, 2\}^*$, denote by $\Gamma(a)$ the tree of $\Gamma$-family $\{B_b\}_{b\in\{1,2\}^*}$ of subsets of $A_a$ such that $B_{b}=A_{ab}$ for each $b\in \{1, 2\}^*$. It is clear that $\Gamma(a)$ is the subtree of tree $\Gamma$ with the root $A_a$.

For an arbitrary subtree $\Gamma(a1)$ (respectively $\Gamma(a2)$) we will call the tree $\Gamma(a)$ a parent tree of $\Gamma(a1)$ (respectively $\Gamma(a2)$).

We write $\Gamma_1< \Gamma_2$ if for all $a\in \{1,2\}^*$, $|A_a|\leq|B_a|$.

We shall say that a full binary tree is a monotone binary tree over set $X$ if each subtree of $\Gamma$ is less than the parent tree of this subtree.

Fix a total order on an $n$-element set $X$ and denote by $Q_n$ the number of the monotone binary trees on $X$.

We give the initial values of $Q_n$, $n\in \mathbb{N}$ below. To count them we have used a computer programm. \begin{array}[t]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n &1&2&3&4&5&6 &7 &8 &9 &10 \\ \hline Q_n &1&1&2&3&6&10&18&32&58&101 \\ \hline \end{array}

The sequence we obtained doesn't match with any in OEIS.

Question: Given a positive integer $n$, how to efficiently compute the number $Q_n$ of monotone full binary trees on an $n$-element set? -- Is there a formula expression for $Q_n$?

Answer 1

As already alluded to in the comments, $Q_n$ is the number of full binary ordered trees with $n$ leaves satisfying an additional condition, which is easily seen to be equivalent to the following: any of the two immediate subtrees below the root is included in the original tree when shifted up one level to align the roots.

The non-local nature of the condition suggests it might be difficult to express $Q_n$ using a recurrence or a generating function, which makes me think one shouldn’t expect a nice formula. However, let me give at least some crude bounds to show that the number has exponential growth rate.

1) A trivial upper bound on $Q_n$ is given by the number of all full binary ordered trees with $n$ leaves, which is the Catalan number $$\frac1n\binom{2(n-1)}{n-1}=O(4^nn^{-3/2}).$$

2) For a lower bound, observe that the extra condition is satisfied automatically for trees of depth $d+1$ that contain all possible nodes of depths $\le d$. So, for $0<p<1$ a constant specified later, let us consider trees containing $\{1,2\}^{\le d}$, where additionally a set of $p2^d$ out of the $2^d$ nodes of depth $d$ split into a pair of nodes of depth $d+1$. These trees have $n=(1+p)2^d$ leaves, and there are $$\binom{2^d}{p2^d}=\Theta\bigl(2^{2^dH(p)}(2^d)^{-1/2}\bigr)=\Theta\bigl(2^{nH(p)/(p+1)}n^{-1/2}\bigr)$$ of them, where $H(p)=-p\log p-(1-p)\log(1-p)$ is the binary entropy function. One checks easily that the exponent $H(p)/(1+p)$ is maximized by setting $p=\varphi^{-2}$, where $\varphi=(1+\sqrt5)/2$ denotes the golden ratio, which gives $$2^{H(p)/(1+p)}=\varphi.$$ Thus, $$Q_n=\Omega(\varphi^nn^{-1/2})$$ for infinitely many $n$.