PROMOTING ACCESS TO AFRICAN RESEARCH

Quaestiones Mathematicae

Log in or Register to get access to full text downloads.

Remember me or Register



DOWNLOAD FULL TEXT Open Access  DOWNLOAD FULL TEXT Subscription or Fee Access

A combinatorial approach for analyzing the number of descendants in increasing trees and related parameters

Markus Kuba, Alois Panholzer

Abstract


This work is devoted to a study of the number of descendants of node j in random increasing trees, previously treated in [5, 8, 10, 15], and also to a study of the number of descendants of node j in pairs of random trees generated by a certain growth process generalizing the corresponding analysis of various classes of random increasing trees. Our analysis is based on a combinatorial approach, which establishes a bijection with certain lattice paths. For the parameters considered we derive closed formulæ for the probability distributions, the expectation and the variance, and obtain limiting distribution results also, extending known results in the literature. Furthermore, the bijective approach enables us to study a weighted version of the number of descendants of node j in random increasing trees. Moreover, we also discuss the multidimensional case, i.e., the joint distribution of the number of descendants of the nodes j1 and j2, and applications.

Keywords: Increasing trees; descendants; growth process; limiting distribution

Quaestiones Mathematicae 32(2009), 91–114



http://dx.doi.org/10.2989/QM.2009.32.1.8.710
AJOL African Journals Online