Asymptotics of increasing trees

This thesis addresses the problem of finding the asymptotic average path length in species of increasing trees. A version of Joyal’s theory of species, L—species, is used to derive power series identities for simple increasing trees and give them bijective proofs. The main identity involved here is an autonomous, nonlinear, ordinary differential equation. Asymptotic results on the number and average path length of these species are derived by analysis of the singularities of these power series when they are treated as analytic functions. The result is a general method for finding the asymptotic number of and asymptotic average path length in increasing trees defined by a single differential equation. In the particular case Where there is a uniform upper bound on the number of descendents a vertex has (and in some other cases) the method can be simply automated using a symbolic algebra package such as MAPLE. It is found that the expected path length of a tree in a species of increasing trees with the above restriction is asymptotically proportional to n log n, where n is the number of vertices in the tree. By contrast, it is shown, using similar combinatorial methods, that labelled, non—increasing trees and unlabelled trees, to which similar analytic methods apply, have path length asymptotically proportional to n*sqrt(n)