algorithmscombinatoricscomputational complexitytrees
Given a integer $h$
What is $N(h)$ the number of full binary trees of height less than $h$?
For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't find any expression of $N(h)$ neither a reasonable upper bound.
Edit In a full binary tree (sometimes called proper binary tree) every node other than the leaves has two children.
Given h...height if tree, N(h).. count of nodes for tree height h. If h = 1: N(h) = 1; h = 2: N(h) = N(1) * 2 = 1 * 2; h = 3: N(h) = N(2) * 2 = N(1) * 2 * 2 = 1 * 2 * 2 * 2; ... h = n: N(n) = N(n-1) * 2 = ... = 1 * 2 * 2 * 2...= 1 * 2^n = 2^n Each node has two children.
So, count of nodes if height of tree is n is N(n) = 2^n. And if count of nodes of full binary tree is N, then height of tree n is proportional to log_2(N) or n = C(log(N)).
Firstly, (c) should be in the $h=2$ row and you are missing a few trees in the $h=3$ row; there should be 21 of them. For the number of full binary trees of a certain height see OEIS A001699.
Now to find $N(h)$. Counting by subtrees is hard and there is hardly any literature on the matter. It's hard because the left and right principal subtrees are not independent. The natural recursion involves taking the union of their subtree-sets. Before you read further, you should check out the related thread. I will relate to a few things from its accepted answer.
A binary tree $\tau$ can be compacted into a unique directed acyclic graph where each node represents a distinct subtree in $\tau$. Now you can represent these DAGs in a canonical form, allowing you to define their "shape". In this sense, the "height" of the DAG corresponds to the height of the tree. For example,
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad$ 
is a possible shape that contains 11 nodes and has a height of 6. Thus it represents a tree of height 6 with 11 subtrees. To find $N(h)$, we need to make the DAG as wide as possible. A node in layer $\ell$ of the DAG represents a tree of height $\ell$, so layer $\ell$ can contain at most $T(\ell)$ nodes. Also, by the canonical definition of the DAGs, the width of the layers can only grow {1,2,4,8,...} from the top down. These two bounds are tight (by the algorithm in the other thread), and can be used to compute $N(h)$. For example, the first few values $(h, N(h), \text{shape})$ are
0 1 [1]
1 2 [1, 1]
2 3 [1, 1, 1]
3 5 [1, 1, 2, 1]
4 8 [1, 1, 3, 2, 1]
5 12 [1, 1, 3, 4, 2, 1]
6 20 [1, 1, 3, 8, 4, 2, 1]
7 36 [1, 1, 3, 16, 8, 4, 2, 1]
8 57 [1, 1, 3, 21, 16, 8, 4, 2, 1]
9 89 [1, 1, 3, 21, 32, 16, 8, 4, 2, 1]
10 153 [1, 1, 3, 21, 64, 32, 16, 8, 4, 2, 1]
The first 200 values of $N(h)$ are listed here.
Best Answer
Here is my contribution to this interesting discussion. Introduce $T_{\le n}(z)$ the OGF of full binary trees of height at most $n$ by the number of nodes. Now a tree of height at most $n$ either has height at most $n-1$ or height exactly $n.$ The latter tree has a subtree of height $n-1$ on the left or the right of the root node or the root has two children of height $n-1.$ This gives $$T_{\le n} = T_{\le n-1} + 2z (T_{\le n-1}-T_{\le n-2})T_{\le n-2} + z(T_{\le n-1}-T_{\le n-2})^2$$ where $T_{\le 0} = 1$ and $T_{\le 1} = z+1.$ Observe that $$T_{=n} = T_{\le n} - T_{\le n-1}.$$ Some algebra produces the simplified form $$T_{\le n} = T_{\le n-1} + z T_{\le n-1}^2 - z T_{\le n-2}^2.$$ This produces e.g. the following generating function for trees of height at most four by the number of nodes: $${z}^{15}+8\,{z}^{14}+28\,{z}^{13}+60\,{z}^{12}+94\,{z}^{11} +116\,{z}^{10}\\+114\,{z}^{9}+94\,{z}^{8}+69\,{z}^{7} +44\,{z}^{6}+26\,{z}^{5}+14\,{z}^{4}+5\,{z}^{3}+2\,{z}^{2}+z+1.$$ For the count compute the sequence $T_{\le n}(1)$ which yields $$1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802,\\ 1947270476915296449559703445493848930452791205,\ldots$$ This is OEIS A003095 and has closed form recurrence $$t_n = t_{n-1} + t_{n-1}^2-t_{n-2}^2$$ with $t_0=1$ and $t_1=2.$ The number of trees of height exactly $n$ is given by $$t_n-t_{n-1}$$ which gives the sequence $$1, 3, 21, 651, 457653, 210065930571, 44127887745696109598901,\\ 1947270476915296449559659317606103024276803403,\ldots$$ which is OEIS A001699.
Remark. Reviewing this post several years later we see that we have not employed the definition of a full binary tree as shown e.g. at Wikipedia because we admit trees where one of the children is a leaf. But the OEIS says we have the right values, how to explain this. We can count full binary trees by not admitting leaves (trees of size zero) so that $T_{\le 0}(z)=0$ and $T_{\le 1}(z) = z.$ This gives starting values for the recurrence as $0$ and $1$ with the next value being $2.$ However $1$ and $2$ are the starting values for ordinary binary trees, which explains the matching values (shift sequence and prepend a zero term). Hence the above calculation goes through. (Note: we take height zero to be the height of a leaf and height one the height of a singleton.)