Limit laws for the Randic index of random binary tree models

作者：Feng Qunqiang; Mahmoud Hosam M^*; Panholzer Alois

来源：Annals of the Institute of Statistical Mathematics, 2008, 60(2): 319-343.

DOI：10.1007/s10463-006-0107-z

• random trees
• binary search trees
• Catalan trees
• recurrence
• moments
• contraction method
• functional equation
• computational chemistry
• chemical index
• topological index

We investigate the Randic index of random binary trees under two standard probability models: the one induced by random permutations and the Catalan (uniform). In both cases the mean and variance are computed by recurrence methods and shown to be asymptotically linear in the size of the tree. The recursive nature of binary search trees lends itself in a natural way to application of the contraction method, by which a limit distribution (for a suitably normalized version of the index) is shown to be Gaussian. The Randic index (suitably normalized) is also shown to be normally distributed in binary Catalan trees, but the methodology we use for this derivation is singularity analysis of formal generating functions.

• 出版日期2008-6