On the structure of random plane-oriented recursive trees and their branches

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Pólya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.