Journal of Applied Mathematics and Stochastic Analysis
Volume 4 (1991), Issue 3, Pages 175-186

On the distribution of the number of vertices in layers of random trees

Lajos Takács1,2

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.


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 nn1 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.