How many trees with height $h$ are there? Given $n, h\in\Bbb{N}$, let $f(n, h)$ be the number of rooted trees with $n$ vertices and height $h$. How can we compute $f$?
Let's denote by $r$ the root of a tree. Here, the height of a tree is the maximum distance between $r$ and one of it's vertices.
What I've noticed so far:

*

*It's easy to see that $h = 1$ can only be achieved by the star graph, so $f(n, 1) = 1$.


*For $h = 2$, notice that the subtrees rooted on the neighborhood of $r$ must have heights of at most $1$, i.e., be star graphs. We have $n-1$ vertices to "spend" on those stars, so the problem becomes finding the number of natural solutions to $x_1 + 2x_2 + \dots + (n-1)x_{n-1} = n-1$ (here, $x_i$ is the number of stars with $i$ vertices), which is $P(n-1)$, the number of partitions of $n-1$. However, we must exclude the solution $(n-1, 0, \dots, 0)$ for which the graph is a star (and have height $1$), so $f(n, 2) = P(n-1)-1$.


*For $h = n-2$, there must be a branch with $n-2$ vertices, so there is exactly one vertex who's not part of this branch and there are $n-2$ possibilities for it's father (it can't be the last vertex of the branch), so $f(n, n-2) = n-2$.


*It's also easy to see that $h = n-1$ can only be achieved by the path graph for which $r$ is one of the extremes, so $f(n, n-1) = 1$.
The case $h=2$ gave me the indication that this can be a very hard problem. I wonder if some form of smart recursion could lead to a relatively simple (or at least computable) solution.
 A: We will look at all possible trees at different heights, let $h_0$ be the root, $h_1$ height $1$, $h_2$ height $2$, $\dots$, and $h_{h}$ height $h$.
Furthermore let $k_i$ be the possible number of vertices at $h_i$.
Thus $k_0 = 1$, namely there is precisely $1$ root. Furthermore $k_1 \in \{1,\dots,(n-1)-(h-1)\}$, namely there must be at least $1$ vertex at height $1$ and there can be at most $(n-1)-(h-1) = n-h$, because there are $n-1$ vertices left at this point, and we still need $h-1$ vertices to reach height $h$.
Next at height $h$ we have $k_2 \in \{1,\dots,(n - 1 - k_1) - (h-2)\}$, because there are $n-1-k_1$ vertices left and we still need $h-2$ to reach height $h$.
Continuing gives $$k_i \in \{1,\dots,(n-1-k_1-\cdots-k_{i-1}) - (h-i)\}$$
for $i \in \{1,\dots,h-1\}$ and for $k_h$ we have
$$k_h = n-1-k_1-\cdots -k_{h-1}$$
because all vertices that are left must be placed at height $h$.
Next we consider the number of possibilities at each height.
On height $h_i$ there are $k_i$ vertices and they are connected in a certain manner with the $k_{i-1}$ vertices at height $h_{i-1}$. Call this number $g_{k_i}$.
We have $g_{k_0} = 1$ and $g_{k_1} = 1$, anyone knowing what the other $g_{k_i}$ are is very welcome at this point!
The last step is to add over all possible $k_i$, this gives
$$
  f(n,h) = g_{k_0} \sum_{k_1=1}^{(n-1)-(h-1)} g_{k_1} \sum_{k_2=1}^{(n-1-k_1)-(h-2)} g_{k_2} \sum_{k_3} \cdots \sum_{k_{h-1}=1}^{(n-1-k_1-\cdots-k_{h-2})-(h-(h-1))} g_{k_{h-1}} g_{k_h}.
$$
This answer is far from complete, but I hope it might give some structure to the problem.
