# Number of binary trees of size $n$ such that all subtrees of same size are equal?

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.

• 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? – D.W. Jan 11 '18 at 18:02
• 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$? – Peter Taylor Jan 12 '18 at 13:05
• @D.W. Unfortunately no progress so far, that's why I posted the question. – Danny Jan 12 '18 at 21:42
• 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. – Danny Jan 12 '18 at 21:49
• 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? – 6005 Mar 3 at 18:08