A Combinatorial Approach for Analyzing the Number of Descendants in Increasing Trees and Related Parameters

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 j ₁ and j ₂, and applications.