The height of random binary unlabelled trees

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.
14 pages

Keywords

Combinatorics, Probability, 05A16 ; 05A15 ; 05C05 ; 60C05

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/164954

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0807.2365
 http://arxiv.org/abs/0807.2365

Collections

arXiv