Automatic Expansion of Generating Functions

Many interesting problems in applications, for instance analysis of algorithms, can be reduced to combinaorial counting problems. However, it is often not possible to get explicit expressions for the numbers of interest and even if this is the case, these expression may give no information on the order of magnitude. One important method to get asymptotic information is to encode the numbers in a generating function. This makes the problem amenable to analytic methods. The general goal of this project is to provide algorithmically applicable tools for obtaining asymptotic expansions for the coefficients of generating functions. In particular it is planned to consider the following topics: 1.The extension and analysis of various notions of admissibility to functions of several variables 2.The asymptotic solution of systems of functional equations, especially in case of not strongly connected dependency graphs 3.Preparing the results for automatic processing and implementing them in MAPLE Ad 1: One approach to obtain coefficients of a generating function is Hayman`s conception of admissibility and its modifications. On the one hand for admissible functions the asymptotic expansion of their coefficients is known, on the other hand such functions satisfy some closure properties which allow us to construct admissible functions from an initial set of admissible functions. Since combinatorial counting problems depending on several parameters lead to generating functions in several variables, it is desirable to extend Hayman`s concept to several variables. Ad 2: Counting problems where the combinatorial structures are defined recursively usually lead to generating functions which are implicitly given by a system of functional equations. The case where the dependency graph of the system is strongly connected is already treated in the literature. Goal of the project is the extension of these results to more general systems of functional equations. Ad 3: For univariate admissible functions there exist already MAPLE packages. It is planned to extend those packages to functions in several variables. Since admissible functions satisfy closure properties they are well suited for automatic processing. For systems of functional equations, it is planned to implement the case of strngly connected depency graphs. For the general case a better understanding of the theoretical background is necessary which is part of the project.

For solving combinatoricl enumeration problems it is often necessary to determine the coefficients of a power series. So called Hayman admissible functions are analytic functions for which the coefficients can be determined in a rather uniform fashion. Moreover, they fulfill certain closure properties. This implies that, given a class of admissible funetion, it is easy to construct further ones and an the other band, checking admissibility can be done by decomposition according to the closure properties. One of the main advances of the project was the extension of admissibility to functions of more than one variable in such a way that they still fulfill closure properties. This was done in two different directions: One class of functions in two variables of a shape which often appears in probabilistic combinatorics. For this class a Software tool (in MAPLE) for checking admissibility has been developped. The second class consists of functions in several variables. This class has application in enumerative combinatorics and streng closure properties as well. Another result was the improvement of previous results by Lefmann and Savicky an the relation between the complexity of a Boolean function and the probability that a random expression consisting of Boolean variables (and their negations) and the logical connectives AND and OR describes this function. This could be achieved by translating the occurring structures into systems of functional equations and analyzing these. Further progress has been achieved in the analysis of tree-like structures. It was possible to study various shape characteristics like profile, node degrees, distances between randomly chosen nodes, node height, leaf heights, ancestor tree size, etc. of several classes of trees, e.g., unlabelled and monotonically labelled trees.