Robin Pemantle and I published Analytic Combinatorics in Several Variables 5 years ago. It has just been reviewed very favourably in Bulletin of the American Mathematical Society, by Bob Sedgewick. Having it mentioned together with Analytic Combinatorics by Flajolet and Sedgewick is high praise.
Tag Archives: ACSV theory
Analytic Combinatorics in Several Variables
Robin Pemantle and I have written a book summarizing over a decade of research. The first draft sent to the publisher is available from the book website. We expect publication in 2013 and welcome feedback on this draft version.
A new method for computing asymptotics of diagonal coefficients of multivariate generating functions
Alexander Raichev and Mark C. Wilson, to appear in Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007).
Let $latex sum_{mathbf{n}inmathbb{N}^d} f_{mathbf{n}} mathbf{x}^mathbf{n}$ be a multivariate generating function that converges in a neighborhood of the origin of $latex mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $latex f_{a_1n,ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.
Note: there is a typo: in Example 3.6, we should have $latex c = ( (L-b)/a, (L-a)/b )$ where $latex L = sqrt{a^2 + b^2}$.
Twenty combinatorial examples of asymptotics derived from multivariate generating functions
Robin Pemantle and Mark C. Wilson, to appear in SIAM Review, June 2008.
Abstract: Let $latex F$ be a power series in at least two variables that defines a meromorphic function in a neighbourhood of the origin; for example, $latex F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $latex F$, uniform in certain explicitly defined cones of directions.
The purpose of this article is to illustrate the use of these techniques on a variety of problems of combinatorial interest. The first part reviews the Morse-theoretic underpinnings of these techniques, and then summarizes the necessary results so that only elementary analyses are needed to check hypotheses and carry out computations. The remainder focuses on combinatorial applications. Specific examples deal with enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, descents and solutions to integer equations. 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. Generating functions derived in these three ways are amenable to our asymptotic analyses, and we state some further general results that apply to these cases.
Asymptotics for generalized Riordan arrays
Mark C. Wilson, Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334 (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).
Abstract: The machinery of Riordan arrays has been used recently by several authors. We show how meromorphic singularity analysis can be used to provide uniform bivariate asymptotic expansions, in the central regime, for a generalization of these arrays. We show how to do this systematically, for various descriptions of the array. Several examples from recent literature are given.
Asymptotics of multivariate sequences, part I: smooth points of the singular variety
Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory Series A 97 (2002), 129-161.
Abstract: Given a multivariate generating function $latex F(z_1 , ldots , z_d) = sum a_{r_1 , ldots , r_d} z_1^{r_1} cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy’s integral formula near singular points of $latex F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $latex F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $latex F$ where the local geometry is more complicated, and for which other methods of analysis are not known.