Loading [MathJax]/extensions/MathZoom.js
Counting Walks in the Quarter Plane
Bousquet-Melou, Mireille
HAL, hal-01574724 / Harvested from HAL
We study planar walks that start from a given point (i_0, j_0), take their steps in a finite set S, and are confined in the first quadrant of the plane. 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^2 y + x y^2)) Q(x, y; t) = xy-xtQ(x, 0; t)-ytQ(O, 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. Petkovsek and the author. In both cases, we work directly from the functional equation.
Publié le : 2002-09-18
Classification:  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-01574724,
     author = {Bousquet-Melou, Mireille},
     title = {Counting Walks in the Quarter Plane},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01574724}
}
Bousquet-Melou, Mireille. Counting Walks in the Quarter Plane. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-01574724/