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.
    Commented Jan 11, 2018 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$ Commented Jan 12, 2018 at 13:05
  • 1
    $\begingroup$ @D.W. Unfortunately no progress so far, that's why I posted the question. $\endgroup$
    – Danny
    Commented Jan 12, 2018 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
    Commented Jan 12, 2018 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$ Commented Mar 3, 2020 at 18:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.