A probabilistic approach to enumeration of Gessel walks

Details A probabilistic approach to enumeration of Gessel walks A probabilistic approach to enumeration of Gessel walks

2009-03-02

arxiv.org/abs/0903.0277v1

Mathematics

Combinatorics

14 pages, 2 figures

Scientific paper

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\v{s}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\v{s}ek and Wilf are solved.

Affiliated with

Also associated with

No associations

Rating

A probabilistic approach to enumeration of Gessel walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A probabilistic approach to enumeration of Gessel walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A probabilistic approach to enumeration of Gessel walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78088