دانلود کتاب Algorithmic and Symbolic Combinatorics: An Invitation to Analytic Combinatorics in Several Variables

فهرست مطالب :

Foreword Preface Contents List of Symbols Chapter 1 Introduction 1.1 Algorithmic Combinatorics 1.1.1 Analytic Methods for Asymptotics 1.1.2 Lattice Path Enumeration 1.2 Diagonals and Analytic Combinatorics in Several Variables 1.2.1 The Basics of Analytic Combinatorics in Several Variables 1.2.2 A History of Analytic Combinatorics in Several Variables 1.3 Organization References Part I Background and Motivation Chapter 2 Generating Functions and Analytic Combinatorics 2.1 Analytic Combinatorics in One Variable 2.1.1 AWorked Example: Alternating Permutations 2.1.2 The Principles of Analytic Combinatorics 2.1.3 The Practice of Analytic Combinatorics 2.2 Rational Power Series 2.3 Algebraic Power Series 2.4 D-Finite Power Series 2.4.1 An Open Connection Problem 2.5 D-Algebraic Power Series Appendix on Complex Analysis Problems References Chapter 3 Multivariate Series and Diagonals 3.1 Complex Analysis in Several Variables 3.1.1 Singular Sets of Multivariate Functions 3.1.2 Domains of Convergence for Multivariate Power Series 3.2 Diagonals 3.2.1 Properties of Diagonals 3.2.2 Representing Series Using Diagonals 3.3 Multivariate Laurent Expansions and Other Series Operators 3.3.1 Convergent Laurent Series and Amoebas 3.3.2 Diagonals and Non-Negative Extractions of Laurent Series 3.4 Sources of Rational Diagonals 3.4.1 Binomial Sums 3.4.2 Irrational Tilings 3.4.3 Period Integrals 3.4.4 Kronecker Coefficients 3.4.5 Positivity Results and Special Functions 3.4.6 The Ising Model and Algebraic Diagonals 3.4.7 Other Sources of Examples Problems References Chapter 4 Lattice Path Enumeration, the Kernel Method, and Diagonals 4.1 Walks in Cones and The Kernel Method 4.1.1 Unrestricted Walks 4.1.2 A Deeper Kernel Analysis: One-Dimensional Excursions 4.1.3 Walks in a Half-Space 4.1.4 Walks in the Quarter-plane 4.1.5 OrthantWalks Whose Step Sets Have Symmetries 4.2 Historical Perspective 4.2.1 The Kernel Method 4.2.2 Recent History of Lattice Paths in Orthants Problems References Part II Smooth ACSV and Applications Chapter 5 The Theory of ACSV for Smooth Points 5.1 Central Binomial Coefficient Asymptotics 5.1.1 Asymptotics in General Directions 5.1.2 Asymptotics of Laurent Coefficients 5.2 The Theory of Smooth ACSV 5.3 The Practice of Smooth ACSV 5.3.1 Existence of Minimal Critical Points 5.3.2 Dealing with Minimal Points that are not Critical 5.3.3 Perturbations of Direction and a Central Limit Theorem 5.3.4 Genericity of Assumptions Problems References Chapter 6 Application: Lattice Walks and Smooth ACSV 6.1 Asymptotics of Highly Symmetric Orthant Walks 6.1.1 Asymptotics for All Walks in an Orthant 6.1.2 Asymptotics for Boundary Returns 6.1.3 Parameterizing the Starting Point Problems References Chapter 7 Automated Analytic Combinatorics 7.1 An Overview of Results and Computations 7.1.1 Surveying the Computations 7.1.2 Minimal Critical Points in the Combinatorial Case 7.1.3 Minimal Critical Points in the General Case 7.2 ACSV Algorithms and Examples 7.2.1 Examples 7.3 Data Structures for Polynomial System Solving 7.3.1 Gröbner Bases and Triangular Systems 7.3.2 Univariate Representations 7.4 Algorithmic ACSV Correctness and Complexity 7.4.1 Polynomial Height Bounds 7.4.2 Polynomial Root Bounds 7.4.3 Resultant and GCD Bounds 7.4.4 Algorithms for Polynomial Solving and Evaluation Problems References Part III Non-Smooth ACSV Chapter 8 Beyond Smooth Points: Poles on a Hyperplane Arrangement 8.1 Setup and Definitions 8.2 Asymptotics in Generic Directions 8.2.1 Step 1: Express the Cauchy Integral as Sum of Imaginary Fibers 8.2.2 Step 2: Determine the Contributing Singularities 8.2.3 Step 3: Express the Cauchy Integral as Sum of Local Contributing Integrals 8.2.4 Step 4: Compute Residues 8.2.5 Step 5: Determine Asymptotics 8.2.6 Dealing with Non-Simple Arrangements 8.3 Asymptotics in Non-Generic Directions Problems References Chapter 9 Multiple Points and Beyond 9.1 Local Geometry of Algebraic and Analytic Varieties 9.2 ACSV for Transverse Points 9.2.1 Critical Points and Stratifications 9.2.2 Asymptotics via Residue Forms 9.3 A Geometric Approach to ACSV 9.3.1 A Gradient Flow Interpretation for Analytic Combinatorics 9.3.2 Attacking the Connection Problem through ACSV and Numeric Analytic Continuation 9.3.3 The State of Analytic Combinatorics in Several Variables Problems References Chapter 10 Application: Lattice Paths, Revisited 10.1 Mostly Symmetric Models in an Orthant 10.1.1 Diagonal Expressions and Contributing Points 10.1.2 Asymptotics for Positive Drift Models 10.1.3 Asymptotics for Negative Drift Models 10.2 Lattice Path Problems to Test Your Skills Problems References Index Author Index