In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a binary tree $t$ if there exists a node $v$ in $t$ such that the tree rooted at this node $v$ equals $t'$.

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$, i.e. the number of nodes that have zero children.

I am interested in the following property of a binary tree $t$: If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. $|t'|=|t''|$, then the subtrees have to be equal, i.e. $t'=t''$. In other words, the number of different subtrees of $t$ that have size $m$ is at most one for each $m$.

Question: What I want to know is the number of different trees of size $n$ fulfilling this property?

I tried some of the usual combinatorial approaches but I made no progress so far.

  • 2
    $\begingroup$ Interesting problem? What are your thoughts so far? Have you made any progress? For instance, have you tried counting the number of such trees of size $n$, for small numbers of $n$? (A program might help.) Have you tried plugging that sequence into OEIS? $\endgroup$ – D.W. Jan 11 '18 at 18:02
  • 1
    $\begingroup$ I don't think it's in OEIS. Anyone want to double-check $1, 1, 2, 5, 14, 40, 120, 357$ for $0 \le n \le 7$? $\endgroup$ – Peter Taylor Jan 12 '18 at 13:05
  • 1
    $\begingroup$ @D.W. Unfortunately no progress so far, that's why I posted the question. $\endgroup$ – Danny Jan 12 '18 at 21:42
  • 1
    $\begingroup$ I did not check for an OEIS sequence so far since I thought it might be possible that this problem is known and somebody can tell me the solution quite fast here. So thanks to @Peter Taylor for checking. $\endgroup$ – Danny Jan 12 '18 at 21:49
  • $\begingroup$ The tree nodes are not labeled, right? And a tree with 1 left child and a tree with 1 right child are considered the same? $\endgroup$ – 6005 Mar 3 '20 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.