Analytic Combinatorics in Several Variables

Introduces the theory of multivariate generating functions, with new exercises, computational examples, and a conceptual overview chapter.

Robin Pemantle (Author), Mark C. Wilson (Author), Stephen Melczer (Author)

9781108836623, Cambridge University Press

Hardback, published 15 February 2024

592 pages
23.6 x 15.8 x 3.7 cm, 1.02 kg

'This book is an invaluable resource that is certain to have dramatic impact on research and teaching in this rapidly developing area of mathematics. The first edition broke new ground; this edition prepares the field for others to harvest new knowledge with important applications in many scientific disciplines.' Robert Sedgewick, Princeton University

Discrete structures model a vast array of objects ranging from DNA sequences to internet networks. The theory of generating functions provides an algebraic framework for discrete structures to be enumerated using mathematical tools. This book is the result of 25 years of work developing analytic machinery to recover asymptotics of multivariate sequences from their generating functions, using multivariate methods that rely on a combination of analytic, algebraic, and topological tools. The resulting theory of analytic combinatorics in several variables is put to use in diverse applications from mathematics, combinatorics, computer science, and the natural sciences. This new edition is even more accessible to graduate students, with many more exercises, computational examples with Sage worksheets to illustrate the main results, updated background material, additional illustrations, and a new chapter providing a conceptual overview.

Part I. Combinatorial Enumeration: 1. Introduction
2. Generating functions
3. Univariate asymptotics
Part II. Mathematical Background: 4. Fourier–Laplace integrals in one variable
5. Multivariate Fourier–Laplace integrals
6. Laurent series, amoebas, and convex geometry
Part III. Multivariate Enumeration: 7. Overview of analytic methods for multivariate generating functions
8. Effective computations and ACSV
9. Smooth point asymptotics
10. Multiple point asymptotics
11. Cone point asymptotics
12. Combinatorial applications
13. Challenges and extensions
Appendices: A. Integration on manifolds
B. Algebraic topology
C. Residue forms and classical Morse theory
D. Stratification and stratified Morse theory
References
Author index
Subject index.

Subject Areas: Discrete mathematics [PBD]