zbMATH — the first resource for mathematics

Counting walks in the quarter plane. (English) Zbl 1026.05004
Chauvin, Brigitte (ed.) et al., Mathematics and computer science II. Algorithms, trees, combinatorics and probabilities. Proceedings of the 2nd colloquium, Versailles-St.-Quentin, France, September 16-19, 2002. Basel: Birkhäuser. Trends in Mathematics. 49-67 (2002).
Summary: We study planar walks that start from a given point \((i_0, j_0)\), take their steps in a finite set of \(\mathbb{Z}^d\), and are confined in the first quadrant \(x\geq 0\), \(y\geq 0\). Their enumeration can be attacked in a systematic way: the generating function \(Q(x,y; t)\) that counts them by their length (variable \(t\)) and the coordinates of their endpoint (variables \(x\), \(y\)) satisfies a linear functional equation encoding the step-by-step description of walks. For instance, for the square lattice walks starting from the origin, this equation reads \[ (xy- t(x+ y+ x^2y+ xy^2)) Q(x,y; t)= xy- xtQ(x, 0;t)- ytQ(0, y;t). \] The central question addressed in this paper is the nature of the series \(Q(x,y;t)\). When is it algebraic? When is it \(D\)-finite (or holonomic)? Can these properties be derived from the functional equation itself?
Our first result is a new proof of an old theorem due to Kreweras, according to which one of these walk models has, for mysterious reasons, an algebraic generating function. Then, we provide a new proof of a holonomy criterion recently proved by M. Petkovšek and the author. In both cases, we work directly from the functional equation.
For the entire collection see [Zbl 0997.00016].

05A15 Exact enumeration problems, generating functions