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