A probabilistic approach to enumeration of Gessel walks

Abstract

We consider Gessel walks in the plane starting at the origin $(0,0)$ remaining in the first quadrant $i,j\ge 0$ and made of West, North-East, East and South-West steps. Let $F(m;n_1,n_2)$ denote the number of these walks with exact $m$ steps ending at the point $(n_1,n_2)$, Petkovšek and Wilf posed several analogous conjectures similar to the famous Gessel's conjecture. We establish a probabilistic model of Gessel walks which is concerned with the problem of vicious walkers. This model helps us to obtain the linear homogeneous recurrence relations with binomial coefficients for both $F(n+k+r;n+k-r,n)$ and $F(n+2k;n,0)$. Precisely, $\frac{n!k!(n+k+1)!}{(2n+2)!}F(2n+2k;0,n)$ is a polynomial with all integer coefficients which leading term is $2^{3k-2}{n}^{2k-2}$, and $\frac{k!(k+1)!}{n+1}F(n+2k;n,0)$ is a polynomial with all integer coefficients which leading term is $n^{2k-1}$. Hence two conjectures of Petkovšek and Wilf are solved.

14 pages, 2 figures

References in corpus (2)

• Proof of Ira Gessel's Lattice Path Conjecture
• Towards a human proof of Gessel's conjecture