4
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ The definition of $\Gamma(a)$ implicitly assumes that $A_{ab}\subseteq A_a$, which doesn’t follow from anything written earlier. Is this condition missing in the definition of a $\Gamma$-family, by any chance? $\endgroup$ Feb 22, 2015 at 12:53
  • $\begingroup$ Yes, I've missed $A_a=A_{a1}\cup A_{a2}$ in item (c) of definition of $\Gamma$-family. $\endgroup$ Feb 22, 2015 at 13:33
  • $\begingroup$ I see, thanks. But then the labels are really redundant, aren’t they? Leaves have to be labelled with elements of $X$ in increasing order, and labels of inner nodes are unions of labels of all leaves below. So, the objects you are counting are just ordered binary trees with $|X|$ leaves and an extra condition on sizes of subtrees. $\endgroup$ Feb 22, 2015 at 16:03
  • $\begingroup$ @EmilJeřábek Yes, you're absolutely right, leaves can be labelled with elements of $X$ in increasing order, and labels of inner nodes are unions of labels of all leaves below. The objects I'm counting are just ordered binary trees with |X| leaves and an extra condition on sizes of subtrees, I understand. The labeles are explained by the fact, that I've used this labels in proofs in the paper and for convenience when address to the nodes. $\endgroup$ Feb 23, 2015 at 16:06

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ The data for $n\le10$ suggest something $(1{.}8)^n$-ish, which means the upper bound has more room for improvement than the lower bound. $\endgroup$ Feb 24, 2015 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.