Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions

DOI10.1137/050643866MaRDI QIDQ3503950zbMATH OpenOpenAlexFDO

Authors Mark C. Wilson, Robin Pemantle

Publication date 10 June 2008

Published in SIAM Review (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0512548

zbMATH Keywords

enumerationkernel methodLagrange inversionmultiple pointresiduesingularitysmooth pointstratified Morse theorytransfer matrix

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Power series, series of functions of several complex variables (32A05)

Abstract: Let $$ be a $d$-dimensional array of numbers, for which the generating function $F(zz):=su{m}_r{a}_{r}z{z}^r$ is meromorphic in a neighborhood of the origin. For example, $F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $F$. Our purpose is to illustrate the use of these techniques on a variety of problems of combinatorial interest. The survey begins by summarizing previous work on the asymptotics of univariate and multivariate generating functions. Next we describe the Morse-theoretic underpinnings of some new asymptotic techniques. We then quote and summarize these results in such a way that only elementary analyses are needed to check hypotheses and carry out computations. The remainder of the survey focuses on combinatorial applications, such as enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, and descents in permutations. After the individual examples, we discuss three broad classes of examples, namely functions derived via the transfer matrix method, those derived via the kernel method, and those derived via the method of Lagrange inversion. These methods have the property that generating functions derived from them are amenable to our asymptotic analyses, and we describe further machinery that facilitates computations for these classes of examples.

Recommendations

• Asymptotics of bivariate analytic functions with algebraic singularities
• Analytic combinatorics in d variables: an overview
• Asymptotics of coefficients of multivariate generating functions: improvements for multiple points
• Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points
• Asymptotics of bivariate analytic functions with algebraic singularities

Cited in

(43)

• Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points
• Asymptotics of subtracted singularities for generating functions with small singularities
• Efficient counting of degree sequences
• Scaling BPS solutions and pure-Higgs states
• Analytic methods in asymptotic enumeration
• Stationary points at infinity for analytic combinatorics
• Skew shape asymptotics, a case-based introduction
• Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
• Asymptotic enumeration of lonesum matrices
• Asymptotics of the extremal excedance set statistic
• Limit theorems for patterns in phylogenetic trees
• Positivity of rational functions and their diagonals
• Weighted lattice walks and universality classes
• Asymptotics of bivariate analytic functions with algebraic singularities
• Combinatorics of locally optimal RNA secondary structures
• Directional complexity and entropy for lift mappings
• Asymptotic properties of free monoid morphisms
• Analytic combinatorics in several variables.
• A case study in bivariate singularity analysis
• Analytic combinatorics in d variables: an overview
• Exact solution of a two-type branching process: clone size distribution in cell division kinetics
• Limit distributions and scaling functions
• scientific article; zbMATH DE number 1552346 (Why is no real title available?)
• Complete monotonicity for inverse powers of some combinatorially defined polynomials
• Double tangent method for two-periodic Aztec diamonds
• Quiver asymptotics: N=1 free chiral ring
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Concavity analysis of the tangent method
• Factorization in the multirefined tangent method
• New software for computing asymptotics of multivariate generating functions
• Diagonal Asymptotics for Products of Combinatorial Classes
• Asymptotics of coefficients of multivariate generating functions: improvements for multiple points
• Coefficient asymptotics of algebraic multivariable generating functions
• Rare event asymptotics for a random walk in the quarter plane
• Two-dimensional quantum random walk
• Asymptotics of multivariate sequences. III: Quadratic points
• Arctic curves of the \(T\)-system with slanted initial data
• Lazy Hermite reduction and creative telescoping for algebraic functions
• Central limit theorems and the geometry of polynomials
• Rigorous analytic combinatorics in several variables in SageMath
• Leaves of preferential attachment trees
• A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics
• Equivalence of ensembles for two-species zero-range invariant measures

This page was built for publication: Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503950)