The complete generating function for Gessel walks is algebraic

DOI10.1090/S0002-9939-2010-10398-2zbMATH Open1206.05013arXiv0909.1965OpenAlexW2023099303MaRDI QIDQ4929975FDOQ4929975

Authors: Alin Bostan, M. Kauers, Mark van Hoeij 

Publication date: 27 September 2010

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Abstract: Gessel walks are lattice walks in the quarter plane $set{N}^2$ which start at the origin $(0,0)inset{N}^2$ and consist only of steps chosen from the set $leftarrow,swarrow,earrow,o$. We prove that if $g(n;i,j)$ denotes the number of Gessel walks of length $n$ which end at the point $(i,j)inset{N}^2$, then the trivariate generating series $G(t;x,y)=su{m}_{n,i,jgeq0}g(n;i,j)x^i{y}^j{t}^n$ is an algebraic function.

Full work available at URL: https://arxiv.org/abs/0909.1965

Recommendations

• Explicit expression for the generating function counting Gessel's walks
• An elementary solution of Gessel's walks in the quadrant
• A human proof of Gessel's lattice path conjecture
• Counting Walks in the Quarter Plane
• On the functions counting walks with small steps in the quarter plane

zbMATH Keywords

generating seriesalgebraic functionlattice walkquarter planeGessel walk

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Classical hypergeometric functions, ({}_2F_1) (33C05) Exact enumeration problems, generating functions (05A15) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Mathematical software, computer programs (educational aspects) (97N80)

Cites Work

• The Magma algebra system. I: The user language
• GFUN
• Complexity of factoring and calculating the GCD of linear ordinary differential operators
• Title not available (Why is that?)
• Walks confined in a quadrant are not always D-finite
• Walks with small steps in the quarter plane
• Automatic Classification of Restricted Lattice Walks
• The complete generating function for Gessel walks is algebraic
• Walks in the quarter plane: Kreweras' algebraic model
• Two non-holonomic lattice walks in the quarter plane
• Fast computation of special resultants
• Modern computer algebra
• Advanced applications of the holonomic systems approach. (Abstract of thesis)
• A probabilistic method for lattice path enumeration
• Proof of Ira Gessel's lattice path conjecture
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Fiber polytopes and fractional power series
• Grothendieck's conjecture for the Risch equation \(y'=ay+b\)
• Differential Operators with Nilpotent p-Curvature

Cited In (54)

• Walks avoiding a quadrant and the reflection principle
• Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
• Algebraic solutions of linear differential equations: an arithmetic approach
• Algebraicity of hypergeometric functions with arbitrary parameters
• Computer algebra in the service of enumerative combinatorics
• Computing characteristic polynomials of p-curvatures in average polynomial time
• Winding of simple walks on the square lattice
• On walks avoiding a quadrant
• Foreword
• Non-D-finite walks in a three-quadrant cone
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• How to generate all possible rational Wilf-Zeilberger pairs?
• The complete generating function for Gessel walks is algebraic
• Extended rate, more GFUN
• Counting quadrant walks via Tutte's invariant method
• Combinatorics meets potential theory
• Non-D-finite excursions in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• Explicit expression for the generating function counting Gessel's walks
• On the denominators of the Taylor coefficients of \(G\)-functions
• An elementary solution of Gessel's walks in the quadrant
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Continued Classification of 3D Lattice Walks in the Positive Octant
• Square lattice walks avoiding a quadrant
• Infinite orders and non-\(D\)-finite property of 3-dimensional lattice walks
• Encoding algebraic power series
• On the nature of the generating series of walks in the quarter plane
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• Walks in the quarter plane: analytic approach and applications
• 3D positive lattice walks and spherical triangles
• Permutations sortable by two stacks in parallel and quarter plane walks
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• On the functions counting walks with small steps in the quarter plane
• On the nature of four models of symmetric walks avoiding a quadrant
• New steps in walks with small steps in the quarter plane: series expressions for the generating functions
• Enumeration of walks with small steps avoiding a quadrant
• On the kernel curves associated with walks in the quarter plane
• Walks in the quarter plane: genus zero case
• Walks obeying two-step rules on the square lattice: full, half and quarter planes
• Linear differential equations as a data structure
• Higher dimensional lattice walks: connecting combinatorial and analytic behavior
• On differentially algebraic generating series for walks in the quarter plane
• Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
• Quadrant walks starting outside the quadrant
• The generating function of Kreweras walks with interacting boundaries is not algebraic
• Proof of two conjectures of Petkovšek and Wilf on Gessel walks
• Automated positive part extraction for lattice path generating functions in the octant
• Lattice walks in the octant with infinite associated groups
• Counting walks in a quadrant: a unified approach via boundary value problems
• A human proof of Gessel's lattice path conjecture
• Counting walks with large steps in an orthant
• Formulae and asymptotics for coefficients of algebraic functions
• Multivariate linear recurrences and power series division

Uses Software

• gfun
• Magma
• GeneratingFunctions

This page was built for publication: The complete generating function for Gessel walks is algebraic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4929975)