Automatic Multivariate Expansion of Generating Functions in Combinatorial Enumeration Problems

01.12.2002 - 31.10.2005
Research funding project
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 strongly connected depency graphs. For the general case a better understanding of the theoretical background is necessary which is part of the project.

People

Project leader

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Publications