Premium
The shape of stretched planar trees
Author(s) -
Maier Robert S.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060220
Subject(s) - limit (mathematics) , infinity , mathematics , planar , combinatorics , tree (set theory) , random tree , limit of a function , statistical physics , discrete mathematics , mathematical analysis , physics , computer science , artificial intelligence , computer graphics (images) , motion planning , robot
We study the asymptotics of a “stretched” model of unlabeled rooted planar trees, in which trees are not taken equiprobable but are weighted exponentially, according to their height. By using standard methods for computing the probabilities of large deviations of random processes, we show that, as the number of vertices tends to infinity, the normalized shape of a random tree converges in distribution to a deterministic limit. We compute this limit explicitly. © 1995 John Wiley & Sons, Inc.