Admissible Functions and Asymptotics for Labelled Structures by Number of Components

Abstract

Let $a(n,k)$ denote the number of combinatorial structures of size $n$ with $k$ components. One often has $\sum_{n,k} a(n,k)x^ny^k/n! = \exp\{yC(x)\}$, where $C(x)$ is frequently the exponential generating function for connected structures. How does $a(n,k)$ behave as a function of $k$ when $n$ is large and $C(x)$ is entire or has large singularities on its circle of convergence? The Flajolet-Odlyzko singularity analysis does not directly apply in such cases. We extend some of Hayman's work on admissible functions of a single variable to functions of several variables. As applications, we obtain asymptotics and local limit theorems for several set partition problems, decomposition of vector spaces, tagged permutations, and various complete graph covering problems.