Analytic Combinatorics proposes a unified treatment of analytic methods in combinatorics. We develop in about 800 pages the basics of asymptotic enumeration and the analysis of random combinatorial structures through an approach that revolves around generating functions and complex analysis. A symbolic framework (Chapters I-III) first provides systematically a large number of exact description of combinatorial models in terms of generating functions. Major properties of generating functions that are of interest in this book are singularities. The text then presents (in Chapters IV-VIII) the core of the theory with two chapters on complex analytic methods focusing on rational and meromorphic functions as well as two chapters on fundamentals of singularity analysis and combinatorial consequences, followed by a chapter on the saddle point method. The last section (Chapters IX) covers multivariate asymptotics and limit laws in random structures. Many examples are given that relate to words, integer compositions and partitions, paths and walks, graphs, mappings and allocations, lattice paths, permutations, trees, and planar maps.
From Birkhäuser:
"This is the second volume in a series of innovative proceedings entirely
devoted to the connections between
mathematics and computer science.
Here mathematics and computer
science are directly confronted and
joined to tackle intricate problems
in computer science with deep and
innovative mathematical
approaches.
The book serves as an outstanding
tool and a main information
source for a large public in applied
mathematics, discrete
mathematics and computer
science, including researchers,
teachers, graduate students and
engineers. It provides an overview
of the current questions in
computer science and the related
modern and powerful
mathematical methods. The
range of applications is very wide
and reaches beyond computer
science."
Return to Philippe Flajolet's Home Page