Number of trees of a certain size

Question

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes.

Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial trees are there?

For example, if $b$ is 2, then the number of partial trees is:

• 1 if $h = 0$
• 4 if $h = 1$
• 25 if $h = 2$
• 676 if $h = 3$

What is the general formula for the number of partial trees, in terms of $b$ and $h$?

thanks in advance, R

Answer 1

Thanks to J.J, I found the following recursive formula on OEIS which does the job:

Let $a(0) = 1$

Let $a(n+1) = (1+a(n))^b$.

Then the number of partial trees is $a(h)$.