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

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

##### MSC:

05A15 | Exact enumeration problems, generating functions |