Journal of Applied Mathematics and Stochastic Analysis
Volume 4 (1991), Issue 3, Pages 175-186
doi:10.1155/S104895339100014X
On the distribution of the number of vertices in layers of random trees
1Case Western Reserve University, Cleveland, Ohio, USA
22410 Newbury Drive, Cleveland Heights 44118, OH, USA
Received 1 May 1991; Revised 1 June 1991
Copyright © 1991 Lajos Takács. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Denote by Sn the set of all distinct rooted trees with n labeled
vertices. A tree is chosen at random in the set Sn, assuming that all the
possible nn−1 choices are equally probable. Define τn(m) as the number
of vertices in layer m, that is, the number of vertices at a distance m
from the root of the tree. The distance of a vertex from the root is the
number of edges in the path from the vertex to the root. This paper is
concerned with the distribution and the moments of τn(m) and their
asymptotic behavior in the case where m=[2αn], 0<α<∞ and n→∞.
In addition, more random trees, branching processes, the Bernoulli
excursion and the Brownian excursion are also considered.