# Counting the forests obtainable by removing subtrees from binary trees

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

• [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}. Commented May 11, 2019 at 16:52
• Maybe some examples would help. Commented May 11, 2019 at 18:19
• So $B_n$ has only one element? Are the leaves of $T'$ roots of the trees of $F_{n,m}$? Commented May 11, 2019 at 18:42
• $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. Commented May 11, 2019 at 18:56
• 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$. Commented May 11, 2019 at 19:58

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, 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.$$
• 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. Commented May 16, 2019 at 10:19
• @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$ Commented May 16, 2019 at 15:19