Parameter studies on random trees and lambda terms

Abstract

This thesis is devoted to asymptotic parameter studies of different combinatorial classes. Thereby the key tools are the concept of generating functions, the symbolic method and singularity analysis. A part of the thesis is devoted to the analysis of tree parameters: We derive asymptotic mean and variance of the protection number of a random tree as well as of a random vertex. in simply generated trees, Polya trees and non-plane binary trees. Then, we compute the avaérage number of non-isomorphic subtree-shapes for two selected classes of increasingly labeled trees. Last, we investigate the average number of embeddings of a given rooted tree into different classes of trees, namely plane and non-plane binary trees and planted plane trees. The last part treats the analysis of shape parameters of special subclasses of lambda terms that are restricted by a bounded length of each binding or a bounded length number of nested abstractions, respectively. In particular, we are able to explain the unusual behaviour of the counting sequence of the latter class by providing their asymptotic unary profile.