A probabilistic approach to enumeration of Gessel walks
| dc.creator | Ping, Sun | |
| dc.date | 2009-03-02 | |
| dc.date.accessioned | 2026-07-07T12:48:09Z | |
| dc.date.available | 2026-07-07T12:48:09Z | |
| dc.description | We consider Gessel walks in the plane starting at the origin $(0, 0)$ remaining in the first quadrant $i, j \geq 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. | |
| dc.description | 14 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/0903.0277 | |
| dc.identifier | http://arxiv.org/abs/0903.0277 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/221955 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15; 05D40 | |
| dc.title | A probabilistic approach to enumeration of Gessel walks | |
| dc.type | text |