Analytic Combinatorics

by Philippe Flajolet , Robert Sedgewick

• ISBN13: 9780521898065
• ISBN10: 0521898064
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-01-19
• Publisher: Cambridge University Press

Summary

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

Preface	p. ix
An Invitation to Analytic Combinatorics	p. 1
Symbolic Methods	p. 13
Combinatorial Structures and Ordinary Generating Functions	p. 15
Symbolic enumeration Methods	p. 16
Admissible constructions and specifications	p. 24
Integer compositions and partitions	p. 39
Words and regular languages	p. 49
Tree structures	p. 64
Additional constructions	p. 83
Perspective	p. 92
Labelled Structures and Exponential Generating Functions	p. 95
Labelled classes	p. 96
Admissible labelled constructions	p. 100
Surjections, set partitions, and words	p. 106
Alignments, permutations, and related structures	p. 119
Labelled trees, mapping, and graphs	p. 125
Additional constructions	p. 136
Perspective	p. 147
Combinatorial Parameters and Multivariate Generating Functions	p. 151
An introduction to bivariate generating functions (BGFs)	p. 152
Bivariate generating functions and probability distributions	p. 156
Inherited parameters and ordinary MGFs	p. 163
Inherited parameters and exponential MGFs	p. 174
Recursive parameters	p. 181
Complete generating functions and discrete models	p. 186
Additional constructions	p. 198
Extremal parameters	p. 214
Perspective	p. 218
Complex Asymptotics	p. 221
Complex Analysis, Rational and Meromorphic Asymptotics	p. 223
Generating functions as analytic objects	p. 225
Analytic functions and meromorphic functions	p. 229
Singularities and exponential growth of coefficients	p. 238
Closure properties and computable bounds	p. 249
Rational and meromorphic functions	p. 255
Localization of singularities	p. 263
Singularities and functional equations	p. 275
Perspective	p. 286
Applications Of Rational and Meromorphic Asymptotics	p. 289
A roadmap to rational and meromorphic asymptotics	p. 290
The supercritical sequence schema	p. 293
Regular specifications and languages	p. 300
Nested sequences, lattice paths, and continued fractions	p. 318
Paths in graphs and automata	p. 336
Transfer matrix models	p. 356
Perspective	p. 373
Singularity Analysis Of Generating Functions	p. 375
A glimpse of basic singularity analysis theory	p. 376
Coefficient asymptotics for the standard scale	p. 380
Transfers	p. 389
The process of singularity analysis	p. 392
Multiple singularities	p. 398
Intermezzo: functions amenable to singularity analysis	p. 401
Inverse functions	p. 402
Polylogarithms	p. 408
Functional composition	p. 411
Closure properties	p. 418
Tauberian theory and Darboux's method	p. 433
Perspective	p. 437
Applications of Singularity Analysis	p. 439
A roadmap to singularity analysis asymptotics	p. 441
Sets and the exp-log schema	p. 445
Simple varieties of trees and inverse functions	p. 452
Tree-like structures and implicit functions	p. 467
Unlabelled non-plane trees and Pólya operators	p. 475
Irreducible context-free structures	p. 482
The general analysis of algebraic functions	p. 493
Combinatorial applications of algebraic functions	p. 506
Ordinary differential equations and systems	p. 518
Singularity analysis and probability distributions	p. 532
Perspective	p. 538
Saddle-Point Asymptotics	p. 541
Landscapes of analytic functions and saddle-points	p. 543
Saddle-point bounds	p. 546
Overview of the saddle-point method	p. 551
Three combinatorial examples	p. 558
Admissibility	p. 564
Integer partitions	p. 574
Saddle-points and linear differential equations	p. 581
Large powers	p. 585
Saddle-points and probability distributions	p. 594
Multiple saddle-points	p. 600
Perspective	p. 606
Random Structures	p. 609
Multivariate Asymptotics and Limit Laws	p. 611
Limit laws and combinatorial structures	p. 613
Discrete limit laws	p. 620
Combinatorial instances of discrete laws	p. 628
Continuous limit laws	p. 638
Quasi-powers and Guassian limit laws	p. 644
Perturbation of meromorphic asymptotics	p. 650
Pertubation of singularity analysis asymptotics	p. 666
Perturbation of saddle-point asymptotics	p. 690
Local limit laws	p. 694
Large deviations	p. 699
Non-Gaussian continuous limits	p. 703
Multivariate limit laws	p. 715
Perspective	p. 716
Appendices	p. 719
Auxiliary Elementary Notions	p. 721
Arithmetical functions	p. 721
Asymptotic notations	p. 721
Combinatorial probability	p. 722
Cycle construction	p. 729
Formal power series	p. 730
Lagrange inversion	p. 732
Regular languages	p. 733
Stirling numbers.	p. 735
Tree Concepts	p. 737
Basic Complex Analysis	p. 739
Algebraic elimination	p. 739
Equivalent definitions of analyticity	p. 741
Gamma function	p. 743
Holonomic functions	p. 748
Implicit Function Theorem	p. 753
Laplace's method	p. 755
Mellin transforms	p. 762
Several complex variables	p. 767
Concepts Of Probability Theory	p. 769
Probability spaces and measure	p. 769
Random variables	p. 771
Transforms of distributions	p. 772
Special distributions	p. 774
Convergence in law	p. 776
Bibliography	p. 779
Index	p. 801
Table of Contents provided by Ingram. All Rights Reserved.