ALCOMFT-TR-03-100

Philippe Flajolet and Robert Sedgewick
Analytic Combinatorics: Basic Complex Asymptotics
INRIA. Work package 4. November 2003.

Abstract: This booklet develops in about 120 pages the basics of asymptotic enumeration through an approach that revolves around generating functions and complex analysis. Major properties of generating functions that are of interest here are singularities. The text presents the core of the theory with two chapters on complex analytic methods focusing on rational and meromorphic functions. It is largely oriented towards applications of complex analysis to asymptotic enumeration and asymptotic properties of random discrete structures. Many examples are given that relate to words, integer compositions, paths and walks in graphs, lattice paths, trees, and constrained permutations.

Postscript file: ALCOMFT-TR-03-100.ps.gz (1238 kb).