Expected height of a random forest

177 Views Asked by At

Consider unlabeled rooted forests with $n$ nodes. What is the expected height of such a forest? I'm actually interested in the asymptotic as $n \to \infty$. Surely it's something like $\log n$, but my searches came up empty, and I imagine I just don't know where to look. Here "height" is the maximal number of nodes in a path starting at a root of a tree in the forest.

Edit: The most relevant OEIS sequence I found was A291336, though it doesn't give much in the way of references or immediately answer the question.

1

There are 1 best solutions below

1
On BEST ANSWER

The average height of an ordered rooted forest with $n$ nodes is known to be asymptotically $\sqrt{\pi n}$. See N. Dershowitz, C. Rinderknecht, “The Average Height of Catalan Treesby Counting Lattice Paths”. (A rooted forest is just a rooted tree with the root removed.)

Because a taller unordered forest can be expected to have less branching and therefore fewer orderings than a shorter unordered forest, the average unordered rooted forest should be a little bit taller than an average ordered rooted forest. Numerical evidence agrees; compare A001853(n + 1)/A000081(n + 1) with A136439(n)/A000108(n):

plot