# Number of n-node binary trees containing an m-node binary subtree

In a paper I see the following lemma about unlabeled binary trees:

If $s_1$ and $s_2$ are both m-node binary trees, then the number of n-node binary trees containing $s_1$ as a subtree is the same as the number of n-node binary trees containing $s_2$.

It goes on to use this to show that if you want to compute the number of n-node binary trees that have m-node as a subtree, it doesn't matter what m-node tree you use.

I feel like I'm either misinterpreting this or missing something obvious. But isn't the following setup a contradiction to this lemma: Nodes 2a and 6a produce the same tree, so tree 1 is only the subtree of 5 4-node trees while tree 2 is a subtree of 6 4-node trees.

• It's probably a good idea to give a link to the paper. Mar 8 '17 at 10:30
• You might be using the wrong definition of "subtree". Also, did you go over the proof of the lemma? Mar 8 '17 at 10:31
• @Yuval Ah yes, I was thinking subgraph instead of subtree. Nodes 3a-6a and 3b-6b do not correspond to 4-node trees containing the original trees as subtrees but rather as subgraphs. This is from Guy Jacobson's thesis. I don't think it is publicly accessible though. Mar 8 '17 at 15:04

You haven't defined what a subtree is, so let's assume that $S$ is a subtree of $T$ if there is a node $x \in T$ whose subtree is isomorphic to $S$ (the notion of isomorphism depends on the definition of subtree).
Now suppose $S_1,S_2$ are two trees on $m$ of vertices. For any tree $T$, mark all the nodes whose subtrees contain $m$ vertices. Define $\pi(T)$ by replacing all such nodes whose subtree is isomorphic to $S_1$ by a subtree isomorphic to $S_2$, and vice versa. For any $n$, this is an involution on the set of trees on $n$ vertices which satisfies the following property: $T$ contains $S_1$ iff $\pi(T)$ contains $S_2$. This shows that the number of trees of size $n$ containing $S_1$ is the same as the number of trees of size $n$ containing $S_2$.