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

algebraic functiongenerating seriesGessel walklattice walkquarter plane

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Classical hypergeometric functions, ({}_2F_1) (33C05) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30) 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

• A probabilistic method for lattice path enumeration
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• 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
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Modern computer algebra
• Proof of Ira Gessel's lattice path conjecture
• The complete generating function for Gessel walks is algebraic
• The Magma algebra system. I: The user language
• 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

(60)

• Encoding algebraic power series
• On the nature of the generating series of walks in the quarter plane
• Lattice walks in the octant with infinite associated groups
• Automated positive part extraction for lattice path generating functions in the octant
• Multivariate linear recurrences and power series division
• Proof of two conjectures of Petkovšek and Wilf on Gessel walks
• On the functions counting walks with small steps in the quarter plane
• On the nature of four models of symmetric walks avoiding a quadrant
• Counting walks with large steps in an orthant
• Walks obeying two-step rules on the square lattice: full, half and quarter planes
• On the kernel curves associated with walks in the quarter plane
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• Walks in the quarter plane: genus zero case
• On differentially algebraic generating series for walks in the quarter plane
• 3D positive lattice walks and spherical triangles
• Winding of simple walks on the square lattice
• On walks avoiding a quadrant
• Linear differential equations as a data structure
• Non-D-finite walks in a three-quadrant cone
• Counting walks in a quadrant: a unified approach via boundary value problems
• Quadrant walks starting outside the quadrant
• The generating function of Kreweras walks with interacting boundaries is not algebraic
• A human proof of Gessel's lattice path conjecture
• Combinatorics meets potential theory
• Infinite orders and non-D-finite property of 3-dimensional lattice walks
• An elementary solution of Gessel's walks in the quadrant
• How to generate all possible rational Wilf-Zeilberger pairs?
• Walks in the quarter plane: analytic approach and applications
• Non-D-finite excursions in the quarter plane
• Permutations sortable by two stacks in parallel and quarter plane walks
• On the denominators of the Taylor coefficients of \(G\)-functions
• The complete generating function for Gessel walks is algebraic
• Counting quadrant walks via Tutte's invariant method
• On 3-dimensional lattice walks confined to the positive octant
• Continued Classification of 3D Lattice Walks in the Positive Octant
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Higher dimensional lattice walks: connecting combinatorial and analytic behavior
• Formulae and asymptotics for coefficients of algebraic functions
• Extended rate, more GFUN
• Foreword
• Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Enumeration of walks with small steps avoiding a quadrant
• 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
• Length derivative of the generating function of walks confined in the quarter plane
• From Kreweras to Gessel: a walk through patterns in the quarter plane
• Differential algebraic generating series of weighted walks in the quarter plane
• The ascent lattice on Dyck paths
• Enumeration of three quadrant walks with small steps and walks on other M-quadrant cones
• Explicit expression for the generating function counting Gessel's walks
• Enumeration and divisibility of higher dimensional king walks
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• Square lattice walks avoiding a quadrant
• New steps in walks with small steps in the quarter plane: series expressions for the generating functions

Describes a project that uses

Uses Software

• Magma
• GeneratingFunctions
• 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)