"On the shape of binary trees"
Mireille Bousquet-Mélou, CNRS, LaBRI Université Bordeaux 1
Take a random binary tree with n nodes, and embed it in Z
2 in
a canonical way: that is, the root of the tree sits at the origin
(0,0), and each right [left] son of a node lies one unit above
and one unit to the right [left] of its father.
Using techniques from enumerative combinatorics and complex analysis,
we shall study the typical shape of this canonical embedding for
large binary trees of a given size. This includes questions like:
how high, how wide is the embedding? What are the horizontal and
vertical profiles of the tree? That is, how many nodes lie at a
given abscissa or ordinate?
The results dealing with the horizontal profile are not new,
while those dealing with the vertical profile are recent
(
http://fr.arxiv.org/abs/math.CO/0501266).
Their main motivation lies in the connection between embeddings
of binary trees and the ISE (Integrated SuperBrownian Excursion).