The complete generating function for Gessel walks is algebraic

DOI10.1090/S0002-9939-2010-10398-2MaRDI QIDQ4929975zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(54)

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

Describes a project that uses

Uses Software

• GeneratingFunctions
• Magma
• gfun

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)