# The complete Generating Function for Gessel Walks is Algebraic

1 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : Gessel walks are lattice walks in the quarter plane $\set N^2$ which start at the origin $(0,0)\in\set 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\set N^2$, then the trivariate generating series $G(t;x,y)=\sum_{n,i,j\geq 0} g(n;i,j)x^i y^j t^n$ is an algebraic function.
Keywords :
Type de document :
Pré-publication, Document de travail
2009
Domaine :

https://hal.inria.fr/hal-00780429
Contributeur : Alin Bostan <>
Soumis le : mercredi 23 janvier 2013 - 22:14:00
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

### Identifiants

• HAL Id : hal-00780429, version 1
• ARXIV : 0909.1965

### Citation

Alin Bostan, Manuel Kauers. The complete Generating Function for Gessel Walks is Algebraic. 2009. 〈hal-00780429〉

### Métriques

Consultations de la notice