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.
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.)
(Partial Answer) First, $N(3)=21$. Second, and probably more useful, you can construct all the trees of height $h$ by adding two children to every non-empty subset of lowest vertices on a tree of height $h-1$. So, if at height $h-1$ you have trees $T_{1},...,T_{n}$ and tree $T_{i}$ has $v_{i}$ vertices on the lowest level, then the number of trees on level $h$ is
$$\sum_{i=1}^{n} (2^{v_{i}}-1).$$
Unfortunately, it seems to be not clear how to count how many leaves are at the lowest level in the newly constructed trees. This does provide an algorithm for constructing all such trees though.
You can define $T(h,b)$ as the number of trees of height $h$ with $b$ leaves at the bottom. Your $N(h)$ is then the sum over $b$ of $T(h,b)$ To get a tree of height $h+1$ and $b$ leaves on the bottom, you pick a tree of height $h$ and at least $b/2$ leaves on the bottom, then pick $b/2$ leaves to hang new leaves from. This gives a recurrence $$T(h+1,b)=\sum_{k=b/2}^{2^h}T(h,k){k \choose b/2}$$ We have $T(3,2)=8, T(3,4)=8, T(3,6)=4, T(3,8)=1$, giving the total of $21$ cited by TravisJ. Then $T(4,2)=8 \cdot 2 + 8 \cdot 4 + 4 \cdot 6 + 1 \cdot 8=80, T(4,4)=8\cdot 1+8\cdot 6 + 4 \cdot 15+1\cdot 28=144, T(4,6)=8\cdot 4+4 \cdot 20+1\cdot 56=168,T(4,8)=8\cdot 1+4\cdot 15+1\cdot 70=138,T(4,10)=4\cdot 6+1\cdot 56=80,T(4,12)=4\cdot 1+1\cdot 28=32,T(4,14)=8,T(4,16)=1$ for a total of $N(4)=651$ The sequence is given in OEIS A001699 where it is said to approach $1.5028368...^{(2^n)}$ and some references are given.
Let's consider all possible ways of constructing a full binary tree of height at most $h \geq 1$. The root has either $0$ or $2$ children, so one possibility is that the tree is just a single node. On the other hand, the number of full binary trees such that the root has two children, is equal to the square of the number of full binary trees of height at most $h - 1$. Therefore, we obtain the recurrence
\begin{align} N(0) & = 1 \\ N(h) & = N(h - 1)^2 + 1 \text{ if } h \geq 1 \end{align}
It follows that $2^{2^{h-1}}$ is a lower bound. On the other hand, $2^{2^{2 h}}$ is an upper bound so the complexity is doubly exponential. I suspect there is a closed form as well.
Note that $N(3) = 26$ here does not disagree with the other answers since they consider trees of height exactly $h$.
