ON THE TOTAL HEIGHTS OF RANDOM ROOTED BINARY-TREES

Denote by S(n) the set of all distinct rooted binary trees with n unla beled vertices. Define sigma(n) as a total height of a tree chosen at random in the set S(n), assuming that all the possible choices are equ ally probable. The total height of a tree is defined as the sum of the heights of its vertices. The height of a vertex in a rooted tree is t he distance from the vertex to the root of the tree, that is, the numb er of edges in the path from the vertex to the root. This paper is con cerned with the distribution and the moments of sigma(n) and their asy mptotic behavior as n --> infinity). (C) 1994 Academic Press, Inc.