دانلود کتاب Analytic Combinatorics

فهرست مطالب :

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