Category Archives: Generating Functions

Probability calculations under the IAC hypothesis

Mark C. Wilson and Geoffrey  Pritchard, Mathematical Social Sciences 54 (2007), 244-256.

Download author version

Abstract: We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.

Twenty combinatorial examples of asymptotics derived from multivariate generating functions

Robin Pemantle and Mark C. Wilson, to appear in SIAM Review, June 2008.

Download author version

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).

Download author version

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.

Probability generating functions for Sattolo’s algorithm

Mark C. Wilson, Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue on probabilistic analysis of algorithms).

Download author version

Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.

The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results results by determining the “grand” probability generating functions of the random variables.

The focus throughout is on using standard methods that give a unified approach, and open the door to further study.

Asymptotics of multivariate sequences, part II: multiple points of the singular variety

Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.

Download author version

Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.

In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.

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.

Download author version

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.