Square lattice walks avoiding a quadrant

Overview & Synopsis

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 < 0 and j < 0}, and then, square lattice walks avoiding the West quadrant Q 2 = {(i, j) : i < j and i < −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 ≥ 0 and j ≥ 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.