Séminaire Lotharingien de Combinatoire, 86B.1 (2022), 12 pp.

Andrew Elvey Price

Enumeration of Walks with Small Steps Avoiding a Quadrant

Abstract. We address the enumeration of walks with weighted small steps avoiding a quadrant. In particular we give an exact, integral-expression solution for the generating function C(x,y;t) counting these walks by length and end-point. Moreover, we determine precisely when this generating function is algebraic, D-finite or D-algebraic with respect to x, showing that this complexity is the same as for walks in the quarter-plane with the same starting point, as long as the starting point (p,q) of the walks lies in the quarter plane then. Finally, we give an integral-free expression for the solution in the cases where (p,q) lies just outside the quarter plane, that is p=0 or q=0 with our convention, proving a conjecture of Raschel and Trotignon.

Received: November 25, 2021. Accepted: March 4, 2022. Final version: April 1, 2022.

The following versions are available: