Some results for monotonically labelled simply generated trees
Bernhard Gittenberger, Alois Panholzer
Abstract
We consider simply generated trees, where the nodes are equipped with weakly monotone labellings with elements of {1, 2, …, r}, for r fixed. These tree families were introduced in [ProUrb1983] and studied further in [Kir1984], [Bli1987], and [MorPro2005]. Here we give distributional results for several tree statistics (the depth of a random node, the ancestor-tree size and the Steiner-distance of p randomly chosen nodes, the height of the j-st leaf, and the number of nodes with label l), which extend the existing results and also contain the corresponding results for unlabelled simply generated trees as the special case r=1.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page