ANALYTIC COMBINATORICS: Contents

PREFACE ix
AN INVITATION TO ANALYTIC COMBINATORICS 1
Part A. SYMBOLIC METHODS 13
- I. COMBINATORIAL STRUCTURES AND ORDINARY GENERATING FUNCTIONS 15
  I. 1. Symbolic enumeration methods 16 I. 2. Admissible constructions and specifications 24 I. 3. Integer compositions and partitions 39 I. 4. Words and regular languages 49 I. 5. Tree structures 64 I. 6. Additional constructions 83 I. 7. Perspective 92
- II. LABELLED STRUCTURES AND EXPONENTIAL GENERATING FUNCTIONS 95
  II. 1. Labelled classes 96 II. 2. Admissible labelled constructions 100 II. 3. Surjections, set partitions, and words 106 II. 4. Alignments, permutations, and related structures 119 II. 5. Labelled trees, mappings, and graphs 125 II. 6. Additional constructions 136 II. 7. Perspective 147
- III. COMBINATORIAL PARAMETERS AND MULTIVARIATE GENERATING FUNCTIONS 151
  III. 1. An introduction to bivariate generating functions (BGFs) 152 III. 2. Bivariate generating functions and probability distributions 156 III. 3. Inherited parameters and ordinary MGFs 163 III. 4. Inherited parameters and exponential MGFs 174 III. 5. Recursive parameters 181 III. 6. Complete generating functions and discrete models 186 III. 7. Additional constructions 198 III. 8. Extremal parameters 214 III. 9. Perspective 218
Part B. COMPLEX ASYMPTOTICS 221
- IV. COMPLEX ANALYSIS, RATIONAL AND MEROMORPHIC ASYMPTOTICS 223
  IV. 1. Generating functions as analytic objects 225 IV. 2. Analytic functions and meromorphic functions 229 IV. 3. Singularities and exponential growth of coefficients 238 IV. 4. Closure properties and computable bounds 249 IV. 5. Rational and meromorphic functions 255 IV. 6. Localization of singularities 263 IV. 7. Singularities and functional equations 275 IV. 8. Perspective 286
- V. APPLICATIONS OF RATIONAL AND MEROMORPHIC ASYMPTOTICS 289
  V. 1. A roadmap to rational and meromorphic asymptotics 290 V. 2. The supercritical sequence schema 293 V. 3. Regular specifications and languages 300 V. 4. Nested sequences, lattice paths, and continued fractions 318 V. 5. Paths in graphs and automata 336 V. 6. Transfer matrix models 356 V. 7. Perspective 373
- VI. SINGULARITY ANALYSIS OF GENERATING FUNCTIONS 375
  VI. 1. A glimpse of basic singularity analysis theory 376 VI. 2. Coefficient asymptotics for the standard scale 380 VI. 3. Transfers 389 VI. 4. The process of singularity analysis 392 VI. 5. Multiple singularities 398 VI. 6. Intermezzo: functions amenable to singularity analysis 401
  VI. 7. Inverse functions 402 VI. 8. Polylogarithms 408 VI. 9. Functional composition 411 VI. 10. Closure properties 418 VI. 11. Tauberian theory and Darboux's method 433 VI. 12. Perspective 437
- VII. APPLICATIONS OF SINGULARITY ANALYSIS 439
  VII. 1. A roadmap to singularity analysis asymptotics 441 VII. 2. Sets and the exp-log schema 445 VII. 3. Simple varieties of trees and inverse functions 452 VII. 4. Tree-like structures and implicit functions 467 VII. 5. Unlabelled non-plane trees and P´olya operators 475 VII. 6. Irreducible context-free structures 482 VII. 7. The general analysis of algebraic functions 493 VII. 8. Combinatorial applications of algebraic functions 506 VII. 9. Ordinary differential equations and systems 518 VII. 10. Singularity analysis and probability distributions 532 VII. 11. Perspective 538
- VIII. SADDLE-POINT ASYMPTOTICS 541
  VIII. 1. Landscapes of analytic functions and saddle-points 543 VIII. 2. Saddle-point bounds 546 VIII. 3. Overview of the saddle-point method 551 VIII. 4. Three combinatorial examples 558 VIII. 5. Admissibility 564 VIII. 6. Integer partitions 574 VIII. 7. Saddle-points and linear differential equations. 581 VIII. 8. Large powers 585 VIII. 9. Saddle-points and probability distributions 594 VIII. 10. Multiple saddle-points 600 VIII. 11. Perspective 606
Part C. RANDOM STRUCTURES 609
- IX. MULTIVARIATE ASYMPTOTICS AND LIMIT LAWS 611 IX. 1. Limit laws and combinatorial structures 613 IX. 2. Discrete limit laws 620 IX. 3. Combinatorial instances of discrete laws 628 IX. 4. Continuous limit laws 638 IX. 5. Quasi-powers and Gaussian limit laws 644 IX. 6. Perturbation of meromorphic asymptotics 650 IX. 7. Perturbation of singularity analysis asymptotics 666 IX. 8. Perturbation of saddle-point asymptotics 690 IX. 9. Local limit laws 694 IX. 10. Large deviations 699 IX. 11. Non-Gaussian continuous limits 703 IX. 12. Multivariate limit laws 715 IX. 13. Perspective 716
Part D. APPENDICES 719
- Appendix A. AUXILIARY ELEMENTARY NOTIONS 721
  A.1. Arithmetical functions 721 A.2. Asymptotic notations 722 A.3. Combinatorial probability 727 A.4. Cycle construction 729 A.5. Formal power series 730 A.6. Lagrange inversion 732 A.7. Regular languages 733 A.8. Stirling numbers. 735 A.9. Tree concepts 737
- Appendix B. BASIC COMPLEX ANALYSIS 739
  B.1. Algebraic elimination 739 B.2. Equivalent definitions of analyticity 741 B.3. Gamma function 743 B.4. Holonomic functions 748 B.5. Implicit Function Theorem 753 B.6. Laplace's method 755 B.7. Mellin transforms 762 B.8. Several complex variables 767
- Appendix C. CONCEPTS OF PROBABILITY THEORY 769
  C.1. Probability spaces and measure 769 C.2. Random variables 771 C.3. Transforms of distributions 772 C.4. Special distributions 774 C.5. Convergence in law 776
BIBLIOGRAPHY 779
INDEX 801