Twenty combinatorial examples of asymptotics derived from multivariate generating functions

Show simple item record Pemantle, R en Wilson, Mark en 2012-03-16T00:10:59Z en 2013-11-15T02:26:58Z en 2008 en
dc.identifier.citation SIAM Review 50(2):199-272 01 Jun 2008 en
dc.identifier.issn 0036-1445 en
dc.identifier.uri en
dc.description.abstract Let {ar : r ∈ Nd} be a d-dimensional array of numbers for which the generating function F(z) := r arzr 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. Wethen 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. en
dc.publisher Society for Industrial and Applied Mathematics en
dc.relation.ispartofseries SIAM Review en
dc.relation.replaces en
dc.relation.replaces 2292/14506 en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from: en
dc.rights.uri en
dc.title Twenty combinatorial examples of asymptotics derived from multivariate generating functions en
dc.type Journal Article en
dc.identifier.doi 10.1137/050643866 en
pubs.issue 2 en
pubs.begin-page 199 en
pubs.volume 50 en
dc.rights.holder Copyright: Society for Industrial and Applied Mathematics en
pubs.end-page 272 en
dc.rights.accessrights en
pubs.subtype Article en
pubs.elements-id 41001 en Science en School of Computer Science en
pubs.arxiv-id math/0512548 en
pubs.record-created-at-source-date 2010-09-01 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace