The quasi-holonomic ansatz and restricted lattice walks
From MaRDI portal
Publication:3534870
DOI10.1080/10236190802332084zbMATH Open1193.05014arXiv0806.4318OpenAlexW2964180469MaRDI QIDQ3534870FDOQ3534870
Authors: M. Kauers, Doron Zeilberger 
Publication date: 5 November 2008
Published in: Journal of Difference Equations and Applications (Search for Journal in Brave)
Abstract: The great enumerator Germain Kreweras empirically discovered this intriguing fact, and then needed lots of pages[K], and lots of human ingenuity, to prove it. Other great enumerators, for example, Heinrich Niederhausen[N], Ira Gessel[G1], and Mireille Bousquet-M'elou[B], found other ingenious, ``simpler proofs. Yet none of them is as simple as ours! Our proof (with the generous help of our faithful computers) is ``ugly in the traditional sense, since it would be painful for a lowly human to follow all the steps. But according to our humble aesthetic taste, this proof is much more elegant, since it is (conceptually) one-line. So what if that line is rather long (a huge partial-recurrence equation satisfied by the general counting function), it occupies less storage than a very low-resolution photograph.
Full work available at URL: https://arxiv.org/abs/0806.4318
Recommendations
Cites Work
- The holonomic ansatz. I: Foundations and applications to lattice path counting
- Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory
- A holonomic systems approach to special functions identities
- Walks confined in a quadrant are not always D-finite
- Walks in the quarter plane: Kreweras' algebraic model
- The method of differentiating under the integral sign
- An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
- A probabilistic method for lattice path enumeration
Cited In (12)
- Proof of Ira Gessel's lattice path conjecture
- On 3-dimensional lattice walks confined to the positive octant
- The computational challenge of enumerating high-dimensional rook walks
- Classifying lattice walks restricted to the quarter plane
- An elementary solution of Gessel's walks in the quadrant
- Square lattice walks avoiding a quadrant
- On the algebraic area of lattice walks and the Hofstadter model
- Counting quadrant walks via Tutte's invariant method (extended abstract)
- INTERACTING QUARTER-PLANE LATTICE WALK PROBLEMS: SOLUTIONS AND PROOFS
- Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
- Computer algebra in the service of enumerative combinatorics
- A human proof of Gessel's lattice path conjecture
Uses Software
This page was built for publication: The quasi-holonomic ansatz and restricted lattice walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3534870)
