Some Applications of Generating Functions for Obtaining Limiting Distribution Results in Random Tree Models

Abstract

In this talk we will discuss several examples of recently obtained limiting distribution results for tree statistics in random tree models, which are obtained via generating functions techniques. In particular we will consider three widely used random tree models:"increasing trees", "simply generated trees" (= Galton-Watson trees) and ?€?binary search trees". For these tree families several probabilistic approaches, as approximating with continuous-time branching processes, using Polya urn models, or applying the contraction method, are well established and give powerful tools in the analysis of a large number of tree statistics. On the other hand it is known that for a variety of tree parameters a combinatorial/analytic approach is also quite fruitful. This we will illustrate on the distributional analysis of several quantities in random trees, like label-based parameters (as the degree of node j in a random tree of size n for j = j(n) growing), the number of subtrees of a given size k = k(n) growing with the tree size n, and so called "topological indices" (as the node-independence number, the path-node covering number, the Randi? index), etc.