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!
Best Answer
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.