Walks confined in a quadrant are not always D-finite

Abstract

We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of Z^2, and always stay in the quadrant x >= 0, y >= 0. We first give a criterion which guarantees that the length generating function of these walks is D-finite, that is, satisfies a linear differential equation with polynomial coefficients. This criterion applies, among others, to the ordinary square lattice walks. Then, we prove that walks that start from (1,1), take their steps in {(2,-1), (-1,2)} and stay in the first quadrant have a non-D-finite generating function. Our proof relies on a functional equation satisfied by this generating function, and on elementary complex analysis.

To appear in Theoret. Comput. Sci. (special issue devoted to random generation of combinatorial objects and bijective combinatorics)

References in corpus (2)

• Walks on the slit plane: other approaches
• Walks on the slit plane

Cited by in corpus (20)

• Walks with small steps in the quarter plane
• Two Non-holonomic Lattice Walks in the Quarter Plane
• Singularity analysis via the iterated kernel method
• On the functions counting walks with small steps in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• On partitions avoiding 3-crossings
• Families of prudent self-avoiding walks
• An elementary solution of Gessel's walks in the quadrant
• On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane
• Weighted Lattice Walks and Universality Classes
• New steps in walks with small steps in the quarter plane
• Enumeration of bilaterally symmetric 3-noncrossing partitions
• Approche galoisienne de la transcendance différentielle
• A proof of the Schinzel-Zassenhaus conjecture on polynomials
• Counting elements and geodesics in Thompson's group $F$
• Walks obeying two-step rules on the square lattice: full, half and quarter planes
• Directed Paths in a Wedge
• Inhomogeneous order 1 iterative functional equations with applications to combinatorics
• A walk in my lattice path garden
• The art of algorithmic guessing in $\text{gfun}$