The complete Generating Function for Gessel Walks is Algebraic

2009/09/10 by Alin Bostan, Manuel Kauers, Bostan, Alin +1 · 4 citations
Computer Science · Mathematics · #05A15 #14N10 #33F10 #68W30 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Symbolic Computation (cs.SC) #semigroups and automata theory

paper · doi:10.48550/arxiv.0909.1965

openalex publication_date 2009/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Gessel walks are lattice walks in the quarter plane \set N² which start at the origin (0,0)∈\set N² and consist only of steps chosen from the set \←,\swarrow,\nearrow,→\. We prove that if g(n;i,j) denotes the number of Gessel walks of length n which end at the point (i,j)∈\set N², then the trivariate generating series G(t;x,y)=∑_{n,i,j≥ 0} g(n;i,j)xⁱ y^j tⁿ is an algebraic function.

Citations

• Theory of Non-Commutative Polynomials

Cited by

• x(1-t(x+x^-1))F(x;t) = x-tF(0;t)
• Weakly-unambiguous Parikh automata and their link to holonomic series
• D-algebraic Guessing
• On the D-finiteness of generating functions counting small steps walks in the quadrant

Related

• On Differentially Algebraic Generating Series for Walks in the Quarter Plane
• Hypergeometric Expressions for Generating Functions of Walks with Small\n Steps in the Quarter Plane
• A probabilistic approach to enumeration of Gessel walks
• Walks with small steps in the quarter plane
• A Note on the Gessel Numbers