2009/03/02 by Ping, Sun
Mathematics · #05A15 #05D40 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.0903.0277
openalex publication_date 2009/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider Gessel walks in the plane starting at the origin (0, 0) remaining in the first quadrant i, j ≥ 0 and made of West, North-East, East and South-West steps. Let F(m; n1, n2) denote the number of these walks with exact m steps ending at the point (n1, n2), 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, (n! k! (n+k+1)!)/((2n+2)!) F(2n+2k;0,n) is a polynomial with all integer coefficients which leading term is 23k-2 n2k-2, and (k! (k+1)!)/(n+1) F(n+2k;n,0) is a polynomial with all integer coefficients which leading term is n2k-1. Hence two conjectures of Petkovšek and Wilf are solved.