zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Analytic combinatorics. (English) Zbl 1165.05001
Cambridge: Cambridge University Press (ISBN 978-0-521-89806-5/hbk). xiii, 810 p. £ 45.00; $ 90.00 (2009).

Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick provides a comprehensive exposition of useful tools for studying the enumeration and asymptotic behavior of combinatorial configurations, with a focus on generating functions. The book begins with an enumerative description of combinatorial structures by means of generating functions. Then, generating functions are interpreted as mappings of the complex plane into itself to determine the asymptotic behavior of the counting sequences. These two methods are applied to a large number of problems and combinatorial structures, for example, compositions, graphs, mappings, partitions, permutations, planar configurations, and words. The combinatorial structures and analytic tools presented are widely applicable and have been selected from a wide variety of research papers by the authors. While there are many books on combinatorics, this book focuses on much needed methods for asymptotic analysis in addition to enumeration.

The book consists of four parts: (A) Symbolic methods (pp. 13–220), (B) Complex asymptotics (pp.221–608), (C) Random structures (pp. 609–718), and (D) Appendices (pp. 719–778).

In Part A, the authors develop the symbolic approach to combinatorial enumeration problems. It contains a unified algebraic theory dedicated to setting up functional relations between counting generating functions. A collection of general theorems provides a systematic translation between combinatorial descriptions and operations on generating functions. Part A contains three chapters: Chapter I deals with unlabeled objects, Chapter II deals with labeled objects, and Chapter III treats multivariate generating functions, which are suitable for the study of combinatorial structures according to several parameters.

Part B focuses on determining the asymptotic behavior of the coefficients of generating functions. General theorems for the asymptotic forms of coefficients of different types of generating functions are given. This part contains five chapters: Chapter IV gives an introduction to analytic methods from complex analysis. Chapter V presents applications and examples of the asymptotic behavior of the coefficients of rational and meromorphic generating functions. In Chapter VI, the authors develop a general singularity theory that covers a wide variety of singularity types, which is followed by 100 pages of applications in Chapter VII. Chapter VIII treats the saddle-point method and gives several combinatorial examples.

In Part C, the authors investigate random combinatorial structures. Topics range from discrete and continuous limit laws, in particular, Gaussian limit laws, to local limit laws, large deviations, and multivariate limit laws. In the process of developing these limit laws, many interesting and important examples of classical combinatorics are treated.

Part D contains three appendices: Appendix A presents some elementary facts of combinatorics and asymptotic analysis. Appendix B gives the necessary background in complex analysis, including analytic functions, the Gamma function, the implicit function theorem, and Mellin transform. Appendix C presents basic notions of probability theory that are useful in analytic combinatorics.

Analytic Combinatorics not only provides a comprehensive theoretical treatment of the topics described above, but also makes for an interesting read: there are thousands of examples from both combinatorics and neighboring areas of science that are often accompanied by beautiful illustrations. It is a self-contained resource and the very general singularity theory developed in it can be applied to many problems, old and new. Analytic Combinatorics can also be used as a text for several courses, for example, Chapters I-III present an introduction to the formal side of combinatorial enumeration. Chapters IV-VIII can be used for a seminar course in either pure or applied mathematics with a focus on the connection between complex analysis, singularity analysis, asymptotics, and (counting) generating functions from combinatorics and other branches of science. This text is a resource that should be on the shelves of everybody who studies asymptotic aspects of enumerative combinatorics and will surely become “the bible” on this topic.


MSC:
05-02Research monographs (combinatorics)
05A15Exact enumeration problems, generating functions
05A16Asymptotic enumeration
60C05Combinatorial probability
60E10Transforms of probability distributions