2
$\begingroup$

Consider the set of rooted labeled trees in which each node may have up to $d$ children. It is well known that the number of such trees with $\leq v$ vertices is (approximately) $(ed)^v$ and that the number of such trees of height $\leq h$ is (approximately) $2^{d^h}$.

I would like to estimate, for a given $v,h$ the number of such trees which have both properties. I am interested in the case in which $v$ is roughly comparable to $h$, say $v \approx \text{poly}(h)$. (Note that it is possible for $v$ to become as large as $d^h$.) I am also interested primarily but not exclusively in the case in which $d$ is small, say even constant.

Are there any good estimates for the number of trees satisfying these criteria?

$\endgroup$
1
  • $\begingroup$ I admit I do not even know whether the generating function can be derived in full generality. However, did you try the method explained in Example 14, Section 3.3 of the species book by Bergeron, Labelle & Leroux, where a functional equation for the binary case is given. Essentially, by adding vertices of a second sort one can balance the tree, i.e., make all subtrees have the same height. $\endgroup$ Oct 6, 2014 at 7:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.