Proof of Ira Gessel's Lattice Path Conjecture

Abstract

We present a computer-aided, yet fully rigorous, proof of Ira Gessel's tantalizingly simply-stated conjecture that the number of ways of walking $2n$ steps in the region $x+y\ge 0,y\ge 0$ of the square-lattice with unit steps in the east, west, north, and south directions, that start and end at the origin, equals $16^n\frac{(5/6{)}_n(1/2{)}_n}{(5/3{)}_n(2{)}_n}$ .

References in corpus (1)

• Walks with small steps in the quarter plane

Cited by in corpus (22)

• Walks with small steps in the quarter plane
• Intervals in the greedy Tamari posets
• Counting quadrant walks via Tutte's invariant method
• Singularity analysis via the iterated kernel method
• On the functions counting walks with small steps in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• An elementary solution of Gessel's walks in the quadrant
• Square lattice walks avoiding a quadrant
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Winding of simple walks on the square lattice
• Permutations sortable by two stacks in parallel and quarter plane walks
• Automatic Classification of Restricted Lattice Walks
• Exact solution of some quarter plane walks with interacting boundaries
• New steps in walks with small steps in the quarter plane
• Hermite Reduction and Creative Telescoping for Hyperexponential Functions
• Explicit expression for the generating function counting Gessel's walks
• Walks avoiding a quadrant and the reflection principle
• A probabilistic approach to enumeration of Gessel walks
• Additive Decompositions in Primitive Extensions
• Walks obeying two-step rules on the square lattice: full, half and quarter planes
• Computation of the Expected Euler Characteristic for the Largest Eigenvalue of a Real Non-central Wishart Matrix
• Walks in the Quarter Plane with Multiple Steps