O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Analytic Combinatorics

Book Description

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.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Contents
  5. Preface
  6. An Invitation to Analytic Combinatorics
  7. Part A. Symbolic Methods
    1. I. Combinatorial Structures and Ordinary Generating Functions
      1. I.1. Symbolic enumeration methods
      2. I.2. Admissible constructions and specifications
      3. I.3. Integer compositions and partitions
      4. I.4. Words and regular languages
      5. I.5. Tree structures
      6. I.6. Additional constructions
      7. I.7. Perspective
    2. II. Labelled Structures and Exponential Generating Functions
      1. II.1. Labelled classes
      2. II.2. Admissible labelled constructions
      3. II.3. Surjections, set partitions, and words
      4. II.4. Alignments, permutations, and related structures
      5. II.5. Labelled trees, mappings, and graphs
      6. II.6. Additional constructions
      7. II.7. Perspective
    3. III. Combinatorial Parameters and Multivariate Generating Functions
      1. III.1. An introduction to bivariate generating functions (BGFs)
      2. III.2. Bivariate generating functions and probability distributions
      3. III.3. Inherited parameters and ordinary MGFs
      4. III.4. Inherited parameters and exponential MGFs
      5. III.5. Recursive parameters
      6. III.6. Complete generating functions and discrete models
      7. III.7. Additional constructions
      8. III.8. Extremal parameters
      9. III.9. Perspective
  8. Part B. Complex Asymptotics
    1. IV. Complex Analysis, Rational and Meromorphic Asymptotics
      1. IV.1. Generating functions as analytic objects
      2. IV.2. Analytic functions and meromorphic functions
      3. IV.3. Singularities and exponential growth of coefficients
      4. IV.4. Closure properties and computable bounds
      5. IV.5. Rational and meromorphic functions
      6. IV.6. Localization of singularities
      7. IV.7. Singularities and functional equations
      8. IV.8. Perspective
    2. V. Applications of Rational and Meromorphic Asymptotics
      1. V.1. A roadmap to rational and meromorphic asymptotics
      2. V.2. The supercritical sequence schema
      3. V.3. Regular specifications and languages
      4. V.4. Nested sequences, lattice paths, and continued fractions
      5. V.5. Paths in graphs and automata
      6. V.6. Transfer matrix models
      7. V.7. Perspective
    3. VI. Singularity Analysis of Generating Functions
      1. VI.1. A glimpse of basic singularity analysis theory
      2. VI.2. Coefficient asymptotics for the standard scale
      3. VI.3. Transfers
      4. VI.4. The process of singularity analysis
      5. VI.5. Multiple singularities
      6. VI.6. Intermezzo: functions amenable to singularity analysis
      7. VI.7. Inverse functions
      8. VI.8. Polylogarithms
      9. VI.9. Functional composition
      10. VI.10. Closure properties
      11. VI.11. Tauberian theory and Darboux’s method
      12. VI.12. Perspective
    4. VII. Applications of Singularity Analysis
      1. VII.1. A roadmap to singularity analysis asymptotics
      2. VII.2. Sets and the exp–log schema
      3. VII.3. Simple varieties of trees and inverse functions
      4. VII.4. Tree-like structures and implicit functions
      5. VII.5. Unlabelled non-plane trees and Pólya operators
      6. VII.6. Irreducible context-free structures
      7. VII.7. The general analysis of algebraic functions
      8. VII.8. Combinatorial applications of algebraic functions
      9. VII.9. Ordinary differential equations and systems
      10. VII.10. Singularity analysis and probability distributions
      11. VII.11. Perspective
    5. VIII. Saddle-Point Asymptotics
      1. VIII.1. Landscapes of analytic functions and saddle-points
      2. VIII.2. Saddle-point bounds
      3. VIII.3. Overview of the saddle-point method
      4. VIII.4. Three combinatorial examples
      5. VIII.5. Admissibility
      6. VIII.6. Integer partitions
      7. VIII.7. Saddle-points and linear differential equations.
      8. VIII.8. Large powers
      9. VIII.9. Saddle-points and probability distributions
      10. VIII.10. Multiple saddle-points
      11. VIII.11. Perspective
  9. Part C. Random Structures
    1. IX. Multivariate Asymptotics and Limit Laws
      1. IX.1. Limit laws and combinatorial structures
      2. IX.2. Discrete limit laws
      3. IX.3. Combinatorial instances of discrete laws
      4. IX.4. Continuous limit laws
      5. IX.5. Quasi-powers and Gaussian limit laws
      6. IX.6. Perturbation of meromorphic asymptotics
      7. IX.7. Perturbation of singularity analysis asymptotics
      8. IX.8. Perturbation of saddle-point asymptotics
      9. IX.9. Local limit laws
      10. IX.10. Large deviations
      11. IX.11. Non-Gaussian continuous limits
      12. IX.12. Multivariate limit laws
      13. IX.13. Perspective
  10. Part D. Appendices
    1. Appendix A. Auxiliary Elementary Notions
      1. A.1. Arithmetical functions
      2. A.2. Asymptotic notations
      3. A.3. Combinatorial probability
      4. A.4. Cycle construction
      5. A.5. Formal power series
      6. A.6. Lagrange inversion
      7. A.7. Regular languages
      8. A.8. Stirling numbers.
      9. A.9. Tree concepts
    2. Appendix B. Basic Complex Analysis
      1. B.1. Algebraic elimination
      2. B.2. Equivalent definitions of analyticity
      3. B.3. Gamma function
      4. B.4. Holonomic functions
      5. B.5. Implicit Function Theorem
      6. B.6. Laplace’s method
      7. B.7. Mellin transforms
      8. B.8. Several complex variables
    3. Appendix C. Concepts of Probability Theory
      1. C.1. Probability spaces and measure
      2. C.2. Random variables
      3. C.3. Transforms of distributions
      4. C.4. Special distributions
      5. C.5. Convergence in law
  11. Bibliography
  12. Index