Proof of Ira Gessel's lattice path conjecture

DOI10.1073/PNAS.0901678106zbMath1203.05010arXiv0806.4300OpenAlexW1995705026WikidataQ46977989 ScholiaQ46977989MaRDI QIDQ3069219

Christoph Koutschan, Manuel Kauers, Doron Zeilberger

Publication date: 24 January 2011

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

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

zbMATH Keywords

walksholonomic ansatzquarter planeGessel walks

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15)

Related Items (28)

Counting quadrant walks via Tutte's invariant method ⋮ An elementary solution of Gessel's walks in the quadrant ⋮ A decomposition of ballot permutations, pattern avoidance and Gessel walks ⋮ Singularity Analysis Via the Iterated Kernel Method ⋮ On the functions counting walks with small steps in the quarter plane ⋮ Non-D-finite excursions in the quarter plane ⋮ Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity ⋮ New steps in walks with small steps in the quarter plane: series expressions for the generating functions ⋮ Computation of the expected Euler characteristic for the largest eigenvalue of a real non-central Wishart matrix ⋮ Counting walks in a quadrant: a unified approach via boundary value problems ⋮ Permutations sortable by two stacks in parallel and quarter plane walks ⋮ How to Generate All Possible Rational Wilf-Zeilberger Pairs? ⋮ On 3-dimensional lattice walks confined to the positive octant ⋮ Multivariate linear recurrences and power series division ⋮ Proof of two conjectures of Petkovšek and Wilf on Gessel walks ⋮ Extended rate, more GFUN ⋮ The complete generating function for Gessel walks is algebraic ⋮ Asymptotics of lattice walks via analytic combinatorics in several variables ⋮ Counting quadrant walks via Tutte's invariant method (extended abstract) ⋮ Explicit expression for the generating function counting Gessel's walks ⋮ Counting walks with large steps in an orthant ⋮ Square lattice walks avoiding a quadrant ⋮ Winding of simple walks on the square lattice ⋮ A human proof of Gessel’s lattice path conjecture ⋮ Walks obeying two-step rules on the square lattice: full, half and quarter planes ⋮ Exact solution of some quarter plane walks with interacting boundaries ⋮ Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior ⋮ A mating-of-trees approach for graph distances in random planar maps

Uses Software

• OEIS
• DEtools

Cites Work

• The method of differentiating under the integral sign
• Classifying lattice walks restricted to the quarter plane
• A holonomic systems approach to special functions identities
• Non-commutative elimination in Ore algebras proves multivariate identities
• Linear recurrences with constant coefficients: The multivariate case
• The quasi-holonomic ansatz and restricted lattice walks

This page was built for publication: Proof of Ira Gessel's lattice path conjecture