Counting Walks in the Quarter Plane

By Mireille Bousquet-M'elou. 2017

61 citations recorded by the source corpus.

We study planar walks that start from a given point (i0j0), take their steps in a finite set \(\mathfrak{S}\), and are confined in the first quadrant x ≥ 0, y ≥ 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 $$\left( {xy - t(x + y + {x^2}y + x{y^2})} \right) {\text{Q(x,y;t)}} {\text{ = }} {\text{xy - xtQ(x,0;t) - ytQ(0,y;t)}}{\text{.}}$$

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/a76af1640027a20637c9a3e9bc02bb8dad5039e2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

1. Marni Mishna
2. Mireille Bousquet-M'elou
3. Kilian Raschel

In Mathematical Physics

1. Marni Mishna
2. Mireille Bousquet-M'elou

Citations in the corpus

• ON PARTITIONS AVOIDING 3-CROSSINGS (2005, unknown): “First of all, a number of equations with a finite diagram have been solved, and shown to have a D-finite solution [3, 4, 5, 18].”
• On 3-Dimensional Lattice Walks Confined to the Positive Octant (2014, unknown): “=2; 1; 1=2;0;1;2;3;4;5]; 1; [ 1;0;1;2;3;4;5;6;7;8;9]; 1; [1;5=3;2;7=3;8=3;3;10=3;11=3;4;13=3;5]; p 3 9 ; [0;1;3=2;2;5=2;3;3;4;5;6;7]; 3 2 p 2; [0;1=2;1;3=2;2;5=2;3;4;5;6;7]; 55 apparentsingularities; [0;1;2;3;4;5;6;7;8;9;11]: Therefore,Lhas6 finitetruesingularities,andthisimpliesthatdegA 1 isatmost6.”
• Walks with small steps in the quarter plane (2008, background): “Ever since it was imported from probability theory to combinatorics, this group has proved useful (in several disguises, like the obstinate, algebraic, or iterated kernel method) to solve various enumeration problems, dealing with walks [11, 13, 15, 33, 40, 41], but also with other objects, like per”
• Walks in the quarter plane: Kreweras’ algebraic model (2004, background): “Taking the difference (an alternative derivation of Kreweras’ result, obtained by considering the product (R(Y0) − xY0)(R(Y1) − xY1), is presented in [5]) and dividing by Y0 − Y1 gives R(Y0) − R(Y1) Y0 − Y1 − x = tx 2R(x) + 2x̄ − 1/t √ (x) , (8)”