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.

  • $\begingroup$ It's probably a good idea to give a link to the paper. $\endgroup$ – Yuval Filmus Mar 8 '17 at 10:30
  • 1
    $\begingroup$ You might be using the wrong definition of "subtree". Also, did you go over the proof of the lemma? $\endgroup$ – Yuval Filmus Mar 8 '17 at 10:31
  • $\begingroup$ @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. $\endgroup$ – kevinAlbs 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$.


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.