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: