Square lattice walks avoiding a quadrant

Abstract

In the past decade, a lot of attention has been devoted to the enumera-tion of walks with prescribed steps confined to a convex cone. In two dimensions, this means counting walks in the first quadrant of the plane (possibly after a linear transformation). But what about walks in non-convex cones? We investigate the two most natural cases: first, square lattice walks avoiding the negative quadrant Q 1 = {(i, j) : i \textless{} 0 and j \textless{} 0}, and then, square lattice walks avoiding the West quadrant Q 2 = {(i, j) : i \textless{} j and i \textless{} --j}. In both cases, the generating function that counts walks starting from the origin is found to differ from a simple D-finite series by an algebraic one. We also obtain closed form expressions for the number of n-step walks ending at certain prescribed endpoints, as a sum of three hypergeometric terms. One of these terms already appears in the enumeration of square lattice walks confined to the cone {(i, j) : i +j $\ge$ 0 and j $\ge$ 0}, known as Gessel's walks. In fact, the enumeration of Gessel's walks follows, by the reflection principle, from the enumeration of walks starting from (--1, 0) and avoiding Q 1. Their generating function turns out to be purely algebraic (as the generating function of Gessel's walks). Another approach to Gessel's walks consists in counting walks that start from (--1, 1) and avoid the West quadrant Q 2. The associated generating function is D-finite but transcendental.

32 p in Journal of Combinatorial Theory, Series A, Elsevier, 2016, Special issue for the 50th anniversary of the journal

References in corpus (4)

• An elementary solution of Gessel's walks in the quadrant
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• A human proof of Gessel's lattice path conjecture
• Automatic Classification of Restricted Lattice Walks

Cited by in corpus (10)

• Counting quadrant walks via Tutte's invariant method
• Winding of simple walks on the square lattice
• Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
• On the nature of four models of symmetric walks avoiding a quadrant
• On sequences of records generated by planar random walks
• 3d positive lattice walks and spherical triangles
• Walks avoiding a quadrant and the reflection principle
• Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
• Discrete harmonic functions in the three-quarter plane
• Stationary Brownian motion in a 3/4-plane: Reduction to a Riemann-Hilbert problem via Fourier transforms