Number of Trees with n Nodes

I am struggling with a question that asks the number of trees that exist with x nodes and max level z. During my research I found that the number of binary trees with x nodes can be obtained by Catalan numbers. However, there is this element of max levels z. I don’t know how that affects the problem. Can anyone provide me any guidance as to how to solve this problem? I obviously do not want a solution. I am trying to understand what is being asked so that I can solve it.

Solutions Collecting From Web of "Number of Trees with n Nodes"

This is not a solution, or even a useful hint, but perhaps these comments will be useful to someone.

Let $t(n,h)$ be the number of binary trees of height $h$ having $n$ nodes; if I understand correctly, you’re to find some sort of usable expression for $t(n,h)$. That appears to me to be a very hard problem.

A few results are easy: $t(h+1,h)=2^h$, $t(n,h)\ne 0$ iff $h<n<2^{h+1}$, $t(2^{h+1}-1,h)=1$, and of course $\sum_h t(n,h)=C_n$, the $n$-th Catalan number. Summing in the other direction, $\sum_n t(n,h)$ is the $h$-th term of OEIS A001699, for which the OEIS entry mentions no closed form. Here’s a table of $t(n,h)$ for $1\le n\le 8$ and $0\le h\le 7$:

$$\begin{array}{l|cccccccc|c}
n\backslash h&0&1&2&3&4&5&6&7&\text{Total}\\ \hline
0&1&&&&&&&&1\\
1&1&&&&&&&&1\\
2&0&2&&&&&&&2\\
3&0&1&4&&&&&&5\\
4&0&0&6&8&&&&&14\\
5&0&0&6&20&16&&&&42\\
6&0&0&4&40&56&32&&&132\\
7&0&0&1&68&152&144&64&&429\\
8&0&0&0&94&376&480&352&128&1430
\end{array}$$

An analysis like the one that leads to the Catalan recurrence for binary trees on $n$ nodes yields a very messy recurrence for $t(n,h)$:

$$t(n+1,h+1)=2\sum_{k=h+1}^nt(k,h)\sum_{i=0}^{h-1}t(n-k,i)+\sum_{k=h+1}^{n-h-1}t(k,h)t(n-k,h)\;.\tag{1}$$

Without the factor of $2$, the double summation counts the number of ways of building a binary tree on $n+1$ vertices whose left subtree has height $h$ and whose right subtree has height less than $h$; doubling this adds the trees whose right subtrees have height $h$ and whose left subtrees have height less than $h$. The last term on the right counts the binary trees on $n+1$ vertices whose left and right subtrees both have height $h$.

$(1)$ does reduce to something reasonable in special cases. For example, it’s easily verified that

$$t(h+2,h)=2\Big(t(h,h-1)+t(h+1,h-1)\Big)$$

for $h\ge 2$.

This is messy enough, however, that I can’t help wondering whether this is the right problem. By the way, it doesn’t appear to help to replace of height h with of height at most h: that just replaces the entries in the table above with cumulative row sums, which don’t appear to be any nicer.

Added: $(1)$ requires that $t(0,0)=1$ and that the empty tree have height $0$. I’ve added a row to the table to reflect this.

Gerry Myerson has found OEIS A073429 and OEIS A073345, which are versions of the table above. Unfortunately, it appears that not much more is known.