Analytic Combinatorics

Analytic Combinatorics is a self-contained treatment of the mathematics underlying the analysis of discrete structures, which has emerged over the past several decades as an essential tool in the understanding of properties of computer programs and scientific models with applications in physics, biology and chemistry. Thorough treatment of a large number of classical applications is an essential aspect of the presentation. Written by the leaders in the field of analytic combinatorics, this text is certain to become the definitive reference on the topic. The text is complemented with exercises, examples, appendices and notes to aid understanding therefore, it can be used as the basis for an advanced undergraduate or a graduate course on the subject, or for self-study. PREFACE •AN INVITATION TO ANALYTIC COMBINATORICS •Part A. SYMBOLIC METHODS I. COMBINATORIAL STRUCTURES AND ORDINARY GENERATING FUNCTIONS I.1. Symbolic enumeration methods I.2. Admissible constructions and specifications I.3. Integer compositions and partitions I.4. Words and regular languages I.5. Tree structures I.6. Additional constructions I.7. Perspective II. LABELLED STRUCTURES AND EXPONENTIAL GENERATING FUNCTIONS II.1. Labelled classes II.2. Admissible labelled constructions II.3. Surjections, set partitions, and words II.4. Alignments, permutations, and related structures II.5. Labelled trees, mappings, and graphs II.6. Additional constructions II.7. Perspective III. COMBINATORIAL PARAMETERS AND MULTIVARIATE GENERATING FUNCTIONS III.1. An introduction to bivariate generating functions (BGFs) III.2. Bivariate generating functions and probability distributions III.3. Inherited parameters and ordinary MGFs III.4. Inherited parameters and exponential MGFs III.5. Recursive parameters III.6. Complete generating functions and discrete models III.7. Additional constructions III.8. Extremal parameters III.9. Perspective •Part B. COMPLEX ASYMPTOTICS IV. COMPLEX ANALYSIS, RATIONAL AND MEROMORPHIC ASYMPTOTICS IV.1. Generating functions as analytic objects IV.2. Analytic functions and meromorphic functions IV.3. Singularities and exponential growth of coefficients IV.4. Closure properties and computable bounds IV.5. Rational and meromorphic functions IV.6. Localization of singularities IV.7. Singularities and functional equations IV.8. Perspective V. APPLICATIONS OF RATIONAL AND MEROMORPHIC ASYMPTOTICS V.1. A roadmap to rational and meromorphic asymptotics V.2. The supercritical sequence schema V.3. Regular specifications and languages V.4. Nested sequences, lattice paths, and continued fractions V.5. Paths in graphs and automata V.6. Transfer matrix models V.7. Perspective VI. SINGULARITY ANALYSIS OF GENERATING FUNCTIONS VI.1. A glimpse of basic singularity analysis theory VI.2. Coefficient asymptotics for the standard scale VI.3. Transfers VI.4. The process of singularity analysis VI.5. Multiple singularities VI.6. Intermezzo: functions amenable to singularity analysis VI.7. Inverse functions VI.8. Polylogarithms VI.9. Functional composition VI.10. Closure properties VI.11. Tauberian theory and Darboux's method VI.12. Perspective VII. APPLICATIONS OF SINGULARITY ANALYSIS VII.1. A roadmap to singularity analysis asymptotics VII.2. Sets and the exp-log schema VII.3. Simple varieties of trees and inverse functions VII.4. Tree-like structures and implicit functions VII.5. Unlabelled non-plane trees and Polya operators VII.6. Irreducible context-free structures VII.7. The general analysis of algebraic functions VII.8. Combinatorial applications of algebraic functions VII.9. Ordinary differential equations and systems VII.10. Singularity analysis and probability distributions VII.11. Perspective VIII. SADDLE-POINT ASYMPTOTICS VIII.1. Landscapes of analytic functions and saddle-points VIII.2. Saddle-point bounds VIII.3. Overview of the saddle-point method VIII.4. Three combinatorial examples VIII.5. Admissibility VIII.6. Integer partitions VIII.7. Saddle-points and linear differential equations VIII.8. Large powers VIII.9. Saddle-points and probability distributions VIII.10. Multiple saddle-points VIII.11. Perspective •Part C. RANDOM STRUCTURES IX. MULTIVARIATE ASYMPTOTICS AND LIMIT LAWS IX.1. Limit laws and combinatorial structures IX.2. Discrete limit laws IX.3. Combinatorial instances of discrete laws IX.4. Continuous limit laws IX.5. Quasi-powers and Gaussian limit laws IX.6. Perturbation of meromorphic asymptotics IX.7. Perturbation of singularity analysis asymptotics IX.8. Perturbation of saddle-point asymptotics IX.9. Local limit laws IX.10. Large deviations IX.11. Non-Gaussian continuous limits IX.12. Multivariate limit laws IX.13. Perspective •Part D. APPENDICES Appendix A. AUXILIARY ELEMENTARY NOTIONS A.1. Arithmetical functions A.2. Asymptotic notations A.3. Combinatorial probability A.4. Cycle construction A.5. Formal power series A.6. Lagrange inversion A.7. Regular languages A.8. Stirling numbers A.9. Tree concepts Appendix B. BASIC COMPLEX ANALYSIS B.1. Algebraic elimination B.2. Equivalent definitions of analyticity B.3. Gamma function B.4. Holonomic functions B.5. Implicit Function Theorem B.6. Laplace's method B.7. Mellin transforms B.8. Several complex variables Appendix C. CONCEPTS OF PROBABILITY THEORY C.1. Probability spaces and measure C.2. Random variables C.3. Transforms of distributions C.4. Special distributions C.5. Convergence in law •BIBLIOGRAPHY •INDEX Analytic Combinatorics Aims To Enable Precise Quantitative Predictions Of The Properties Of Large Combinatorial Structures. The Theory Has Emerged Over Recent Decades As Essential Both For The Analysis Of Algorithms And For The Study Of Scientific Models In Many Disciplines, Including Probability Theory, Statistical Physics, Computational Biology, And Information Theory. With A Careful Combination Of Symbolic Enumeration Methods And Complex Analysis, Drawing Heavily On Generating Functions, Results Of Sweeping Generality Emerge That Can Be Applied In Particular To Fundamental Structures Such As Permutations, Sequences, Strings, Walks, Paths, Trees, Graphs And Maps. This Account Is The Definitive Treatment Of The Topic. The Authors Give Full Coverage Of The Underlying Mathematics And A Thorough Treatment Of Both Classical And Modern Applications Of The Theory. The Text Is Complemented With Exercises, Examples, Appendices And Notes To Aid Understanding. The Book Can Be Used For An Advanced Undergraduate Or A Graduate Course, Or For Self-study. Symbolic Methods -- Combinatorial Structures And Ordinary Generating Functions -- Labelled Structures And Exponential Generating Functions -- Combinatorial Parameters And Multivariate Generating Functions -- Complex Asymptotics -- Complex Analysis, Rational And Meromorphic Asymptotics -- Applications Of Rational And Meromorphic Asymptotics -- Singularity Analysis Of Generating Functions -- Applications Of Singularity Analysis -- Saddle-point Asymptotics -- Random Structures -- Multivariate Asymptotics And Limit Laws -- Appendix A : Auxiliary Elementary Notions -- Appendix B : Basic Complex Analysis -- Appendix C : Concepts Of Probability Theory. Philippe Flajolet & Robert Sedgewick. Includes Bibliographical References (p. 779-800) And Index. "Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the analysis of algorithms and for the study of scientific models in many disciplines, including probability theory, statistical physics, computational biology and information theory. With a careful combination of symbolic enumeration methods and complex analysis, drawing heavily on generating functions, results of sweeping generality emerge that can be applied in particular to fundamental structures such as permutations, sequences, strings, walks, paths, trees, graphs and maps. This account is the definitive treatment of the topic. In order to make it self-contained, the authors provide full coverage of the underlying mathematics and give a thorough treatment of both classical and modern applications of the theory. The text is complemented with exercises, examples, appendices and notes throughout the book to aid understanding. The book can be used as a reference for researchers, as a textbook for an advanced undergraduate or a graduate course on the subject, or for self-study."--Page 4 of cover "Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the analysis of algorithms and for the study of scientific models in many disciplines, including probability theory, statistical physics, computational biology and information theory. With a careful combination of symbolic enumeration methods and complex analysis, drawing heavily on generating functions, results of sweeping generality emerge that can be applied in particular to fundamental structures such as permutations, sequences, strings, walks, paths, trees, graphs and maps." "This account is the definitive treatment of the topic. In order to make it self-contained, the authors provide full coverage of the underlying mathematics and give a thorough treatment of both classical and modern applications of the theory. The text is complemented with exercises, examples, appendices and notes throughout the book to aid understanding. The book can be used as a reference for researchers, as a textbook for an advanced undergraduate or a graduate course on the subject, or for self-study."--Jacket