Counting full m-ary trees with height H. I'm trying to model certain stochastic process with context trees, but I'm stuck in a combinatorics problem of counting the number of possible full $m$-ary trees with a maximum height $H$.
A full $m$-ary tree is a rooted tree where each node has either $0$ or $m$ children, labeled $1,\dots, m$. I'm calling the height of the tree the maximum distance between the tree's root and its leaves. Since the tree can be identified by its set of leaf paths, I tried to list the first cases with $m = 3$ to understand the recursion:
$a(0) = 1$: Only the tree that is the root itself.
$a(1) = 1+1 = 2$: $\{\text{root}, \{1,2,3\}\}$
$a(2) = 1+1+7$: $\{\text{root}, \{1,2,3\}, \{11,12,13,2,3\}, \{1,21, 22, 23,3\}, \{1,2,31, 32, 33\}, \{11, 12,13, 21,22,23, 3\}, \{1, 21,22,23,31, 32, 33 \}, \{11, 12, 13,2,31,32,33\}, \{11, 12, 13, 21, 22, 23,31, 32, 33\}\}$
It is clear that I can express
$$a(n+1) = a(n) + b(n+1)$$
The problem is that I cannot give an expression for the term $b(n)$. It is the number of trees with at least one leaf $n$-distant from the root, but I can't seem to find an expression for it.
Also, I don't know exactly if these are the correct naming for the terms I'm using and maybe I just failed to search the proper keywords, but even indication of more conventional wording for this problem will be helpful. Thank you!
 A: According to OEIS A003095, the number of full binary trees of height at most $n$ satisfies the recurrence $a_{n+1}=a_n^2+1$; OEIS A135361 says that the number of full ternary trees of height at most $n$ satisfies the recurrence $a_{n+1}=a_n^3+1$. (They don’t specify full trees, but these numbers agree with my counts for full trees up to height $3$.) OEIS doesn’t show any nice closed forms.
These immediately suggest that the corresponding sequence for $m$-ary trees might satisfy the recurrence $a_{n+1}=a_n^m+1$, and indeed it does. Let $T$ be a full $m$-ary tree of height at most $n+1$. If $T$ is not the trivial tree with a single node, the root, let $T_1,\ldots,T_m$ be the subtrees whose roots are the children of the root of $T$. These are full $m$-ary trees of height at most $n$, so there are $a_n$ of them, and there are $a_n^m$ possible choices for $\langle T_1,\ldots,T_m\rangle$, so there are $a_n^m$ such trees $T$. Add the trivial tree, and we have the recurrence $a_{n+1}=a_n^m+1$.
I don’t hold out much hope for a nice closed form, however.
