3
$\begingroup$

Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).

For any rooted tree $T$, we denote by $r(T)$ its root. For instance, $r(B_3)$ is the root of the perfect binary tree having height $3$.

Let $F_{h,m}$ be the set of all possible forests that (i) are formed by at most $m>1$ trees and (ii) can be obtained by removing from any tree $B_{h}$ (for all $h>1$) all nodes (together with their incident edges in $B_h$) of any subtree $T'$ of $B_h$ rooted at $r(B_h)$ (thus we have $r(T')=r(B_h)$).


Question: How can we calculate (or bounding from above) the cardinality of $F_{h,m}$ asymptotically when $h\to\infty$ (as a function of $m$ and $h$)? Does the bound $|F_{h,m}|\le\sum_{i=0}^m \binom{2^h}{i}$ hold for all $h, m>1$?

$\endgroup$

This question has an open bounty worth +50 reputation from Penelope Benenati ending in 19 hours.

The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.

  • 3
    $\begingroup$ [Cool question] I think I’m unsure about your definition of $B_n$. There is only one binary tree with 2^h leaves and height h. Do you mean something involving labelling the vertices? Or maybe you mean instead “B_n is the set of all rooted binary trees with n leaves where each internal node has exactly two children.” In this second interpretation, |B_n| is given by the Catalan numbers. I’m also not sure I understand the definition of F_{n,m}. $\endgroup$ – Pat Devlin May 11 at 16:52
  • 2
    $\begingroup$ Maybe some examples would help. $\endgroup$ – Pietro Majer May 11 at 18:19
  • 2
    $\begingroup$ So $B_n$ has only one element? Are the leaves of $T'$ roots of the trees of $F_{n,m}$? $\endgroup$ – Pietro Majer May 11 at 18:42
  • 1
    $\begingroup$ $B_n$ cannot be infinite as it bounds the number of leaves in the tree. The current definition implies that $B_n$ is nonempty only if $n=2^h$, in which case it contains a single element. $\endgroup$ – Max Alekseyev May 11 at 18:56
  • 1
    $\begingroup$ I mean that, given any $T\in B_h$, $T'$ can be any subtree of $T$ such that (i) the root of $T'$ is the same root of $T$, and (ii) the number of subtrees of $T$ that we obtain by removing all nodes of $T'$ from $T$ (together with all incident edges in $T$), is equal to $m$. $\endgroup$ – Penelope Benenati May 11 at 19:58
5
$\begingroup$

It is convenient to consider the vertex set of $B_h$ as a partially ordered set with its natural genealogic order, with minimum element its root. Any subtree $T'$ as described in your procedure (also including the empty tree) is then exactly an initial segment. (For the notation: $B_1$ is the one-vertex tree, and so on)

Removing $T'$ from $B_h$ leaves a set of $m$ complete trees, whose $m$ roots constitue exactly an $m$-antichain in the partial order. The only $0$-antichain is the empty set and produces the empty forest. The $1$-antichains are the vertices as singletons; there are $2^{h}-1$ of them, including the root. The number of forests with exactly $m$ trees in $B_h$ obtained removing a $T'$ is therefore the number $a_{h,m}$ of all $m$-antichains in $B_h$. So in your question $|F_{h,m}|=\sum_{2\le j\le m}a_{h,j}$, since you like to consider forests with more than one, and no more than $m$ trees. There is a clear convolution formation passing from antichains in $B_h$ to antichains in $B_{h+1}$, giving the recursive relation for the generating polynomial $P_h(x):=\sum_{m\ge0}a_{h,m}x^m$, $$\cases{P_{0}(x)=1\\P_{h+1}(x)=x+P_h(x)^2.}$$

(and of course $P_{h}(x)/(1-x)$ counts antichains with at most $m$ elements in $B_h$). The problem of counting antichains in posets is well-studied. Here is a 2006 paper "Counting chains and antichains in the complete binary tree" you may want to request to the authors (Though I'm not sure if it address the $m$-element version). Incidentally, note that $P_h(1)$, the number of all antichains in $B_h$, is the sequence A003095.

Edit. In fact, if you want an asymptotics for $a_{h,m}$ as $h\to+\infty$ for each fixed $m$, this is easily available: It follows by induction that for any $m$ $$a_{h,m} \sim {2^{mh}\over m!} \quad\text{ as }\;h\to+\infty, $$ so that the bound given by Emil Jeřábek in comment below in terms of $m$-elements subsets of $B_h$ is also an asymptotic, since $$ {2^{mh}\over m!} \sim { 2^{h}-1\choose m } \quad\text{as }h\to+\infty. $$ Indeed we have, for $m=1$: $$a_{h,1} =2^{h}-1\sim 2^{h}\quad\text{as }h\to+\infty,$$ while for $m>1$, $$a_{h+1,m}=\sum_{j=0}^m a_{h,j}a_{h,m-j}= 2a_{h,m}+\sum_{j=1}^{m-1} a_{h,j}a_{h,m-j}$$ so assuming by complete induction hypothesis that $a_{h,j}\sim {2^{jh}\over j!}$ as $h\to+\infty$ holds for each $ j<m$, we find $$a_{h+1,m}- 2a_{h,m}\sim {2^{mh}\over m!}\, \sum_{j=1}^{m-1} {m!\over j!(m-j)!} \,=\,{ 2^m-2\over m!} \,2^{mh}$$ or, dividing by $2^ {h+1 }$ $${a_{h+1,m}\over2^{ h+1 }}- {a_{h ,m}\over2^{ h }}\sim { 2^{m-1}-1\over m!}\,2^{(m-1)h} $$ whence, summing from $0$ to $h-1$ $${a_{h ,m}\over 2^{ h }}\sim {2^{m-1}-1\over m!}\,\sum_{j=0}^{h-1}2^{(m-1)j}={2^{(m-1)h}-1\over m!}\sim{2^{(m-1)h}\over m!} $$ so that $$a_{h,m} \sim {2^{mh}\over m!} \quad\text{as }h\to+\infty.$$

$\endgroup$
  • $\begingroup$ Rmk: in the second paragraph I wrote, leaves is meant as third-person singular of to leave, not as plural of leaf. This topic is irredeemably doomed with ambiguity :( $\endgroup$ – Pietro Majer May 16 at 9:06
  • 1
    $\begingroup$ One might note that the number of $m$-element antichains is trivially at most $\binom{2^h-1}m$ (the number of all $m$-element subsets), which implies the bound at the end of the question. $\endgroup$ – Emil Jeřábek May 16 at 10:19
  • $\begingroup$ @EmilJeřábek in fact your bound is really accurate, for the number of $m$-element antichains turns out to be asymptotic to that of all $m$-elements subsets for $h\to\infty$ for each fixed $m$ $\endgroup$ – Pietro Majer May 16 at 15:19
  • $\begingroup$ Thank you very much Pietro! :) $\endgroup$ – Penelope Benenati May 16 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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