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