Counting the forests obtainable by removing subtrees from binary trees

Question

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

Answer 1

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