The complete Generating Function for Gessel Walks is Algebraic

Abstract

Gessel walks are lattice walks in the quarter plane $\{N{\}}^2$ which start at the origin $(0,0)\in \{N{\}}^2$ and consist only of steps chosen from the set $\{\leftarrow ,\swarrow ,\nearrow ,\to \}$. We prove that if $g(n;i,j)$ denotes the number of Gessel walks of length $n$ which end at the point $(i,j)\in \{N{\}}^2$, then the trivariate generating series $G(t;x,y)={\sum }_{n,i,j\ge 0}g(n;i,j)x^i{y}^j{t}^n$ is an algebraic function.

Cited by in corpus (1)

• Automatic Classification of Restricted Lattice Walks