Welcome to the homepage for the Multivariate Generating Functions Project. To gain maximum value from this site, you will need to know about generating functions and their uses. Good first references are the Wikipedia article generating function, followed by Herbert Wilf's book generatingfunctionology.

This page gives an overview of the subject. The sidebar contains navigational and informational links. The pages are maintained by Mark Wilson and there is inevitably a bias toward work in which he has been involved, in particular the project Asymptotics of Multivariate Sequences. We welcome contributions from anyone working in the area - please contact Mark Wilson.

Why mvGFs

Interesting multivariate sequences are ubiquitous in mathematics and applications. The best all-round tool for studying such sequences is the (multivariate) generating function or mvGF. There are two main questions: finding a nice functional form for the GF of a sequence, and the inverse problem of describing the terms of the sequence given a form for the GF.

There is a noticeable lack of communication between workers in the various application areas that use mvGFs, with many results being discovered more than once. Part of the problem is that "multivariate generating functions" is not really recognized as a coherent mathematical area. The main purposes of this site are to advocate for it being so recognized, and to facilitate the joint work that is essential for further progress.

Finding mvGFs

There is a double meaning in the title: by "finding" we mean determining as a solution to some functional equation, and also locating in the literature.

A recurrence with adequate initial conditions normally determines a GF. However, the solution of these equations is much more difficult in several variables than in the univariate case. The recursive structure of the problem leads directly to a system of functional equations for the GF. A common short-cut is the so-called "symbolic method" (also known as Schutzenberger methodology - see Analytic combinatorics) translates a formal specification of a combinatorial class (in terms of a formal grammar) into the GF that counts the number of objects of a given size, without explicit mention of recurrences satisfied by the counting sequence.

For example, in one variable a constant coefficient linear recurrence yields a rational GF regardless of initial condition; in several variables much more variety is possible (see work of Mireille Bousquet-Mélou and Marko Petkovsek). The so-called kernel method has been used often to solve functional equations determining algebraic GFs. Extending the scope of this method is desirable. Similarly the quadratic method of Tutte is used to solve certain functional equations mostly arising in graph theory. The main expert in this area is Mireille Bousquet-Mélou.

The 2000 Mathematics Subject Classifications most relevant to generating functions as an object of study in their own right are in section 05A Enumerative combinatorics, especially 05A15 (exact enumeration problems, generating functions) and 05A16(asymptotic enumeration). Areas making reasonably heavy use of generating functions are 05 (Combinatorics), 11 (number theory), 33 (special functions), 60 (probability theory and stochastic processes), 68 (computer science), 82 (statistical mechanics). Particularly interesting applications are found in: analysis of algorithms and data structures (68P05, 68Q25, 68W40); queueing theory (60K25, 68M20, 90B22); analytic number theory (e.g. 11N45); polyominoes (05B50).

Analysis of mvGFs

This normally means: extracting information on the coefficients of a given mvGF. One can do this exactly or use asymptotic approximations. The latter is normally more useful, as the exact expressions are usually too complicated to derive and/or understand.

Many difficulties arise in asymptotic extraction. In 1 variable, asymptotics of coefficients of rational GFs can be routinely obtained by residue theory. However, even two-variable rational functions can exhibit much more complicated behaviour. The ongoing project Asymptotics of Multivariate Sequences by Robin Pemantle, Mark Wilson and others has developed methods for computationally effective asymptotic coefficient extraction from an explicitly given meromorphic, non-entire GF. These methods are based on using complex analysis and oscillatory integrals to analyse singularities of explicitly known GFs. The local geometry of the singular variety plays a major role in the analysis.

References

Here is a purposely short and subjectively chosen list of recommended reading. Some other resources:

People

Please send us email if you would like to be included as someone interested in the topic. If you want to specify your interests in more detail please do so.

Robin Pemantle | Mark Wilson | Yuliy Baryshnikov | Manuel Lladser | Alexander Raichev | Mark Ward |

Last updated: 2006-12-19.