The height of unlabelled binary trees

Many properties of a uniformly chosen labelled trees are known. The
approaches that have been used are both probabilistic (based on
branching processes and random walks) and analytic (based on recursive
description and generating functions). When the trees are not labelled
anymore, the symmetries play a crucial role and the classical
probabilitic techniques relying on a natural ordering of the vertices
do not apply any longer. The analytic techniques, however, can still
be used at the moderate additionnal cost. 

We will show the generating function technology can be applied to
describe the depths in a uniformly chosen unlabelled binary tree. We
will then compare the results to the known equivalents for labelled
trees and continuous limit objects like Brownian excursions and
continuous random trees.


This is joint work with P. Flajolet