2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ It seems like there might not be a nice closed formula. Here's the corresponding sequence in OEIS for $b=2$: oeis.org/A004019 $\endgroup$
    – J. J.
    Jan 22, 2014 at 15:10
  • $\begingroup$ Thanks JJ that is super-helpful :) $\endgroup$ Jan 22, 2014 at 16:07

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .