Premium
On the altitude of specified nodes in random trees
Author(s) -
Prodinger Helmut
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080405
Subject(s) - combinatorics , graph , mathematics , discrete mathematics , computer science , algebra over a field , pure mathematics
is called a simply generated family of trees. Such an equation describes how trees are built up recursively. Here the ci are some non-negative constants. For instance, by taking all ci equal to 1, we obtain the family of ordered trees. The altitude of a node is the distance between the roor and this node. (The altitude of the root is zero.) Meir and Moon 121 have studied (among other things) the average number p(n, k ) of nodes of altitude k in a random tree with n nodes. They obtain a generating function which allows them to determine the asymptotic behavior of p(n, k ) and to compute exact expressions for several families of trees. In [ I ] Kemp deals with similar problems. There ordered trees are considered only; changing the notation slightly, p(n , k ) and the higher moments are computed. Furthermore the average number p(t; n, k ) of nodes of altitude k and degree t is introduced. p( t ; n, k ) and the higher moments are found by a computational approach. It is claimed in [l] that the methods of Meir and Moon are not appropriate for these new questions with the parameter t and that they do not give an approach to enumeration results.