# 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.

-
Since you mention levels, these must be rooted trees. Are they binary trees, as suggested by your comment, or rooted trees in general? – Brian M. Scott Jul 10 '12 at 18:33
I believe it is referring to binary tree's. – Rob B. Jul 10 '12 at 18:35
You should probably try to count the number of trees with at least $z+1$ levels and $x$ nodes. – tomasz Jul 10 '12 at 19:16

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.

-
Through $n=6$, your table agrees with oeis.org/A073429, but then the numbers diverge. I wonder whether there isn't a mistake somewhere. See also oeis.org/A073345. – Gerry Myerson Jul 11 '12 at 9:17
@Gerry: I miscalculated $t(7,3)$; the other divergences were knock-on effect. Thanks very much: somehow I missed OEIS A073429 and OEIS A073345, despite their being exactly what I wanted. – Brian M. Scott Jul 11 '12 at 19:28
I'm tempted to +1 even for the amount of work you put into the matrix and all the symbols in your answer. :) – Mihai Danila Jun 20 '13 at 4:50