Proof of Ira Gessel's Lattice Path Conjecture

2008/06/26 by Manuel Kauers, Christoph Koutschan, Doron Zeilberger · 1 citation
Mathematics · #math.CO #msc:05A15 #msc:33F10

paper · pdf · doi:10.1073/pnas.0901678106

arxiv created 2008/06/26 · arxiv updated 2015/05/12

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 ≥ 0, y ≥ 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ⁿ((5/6)_n(1/2)_n)/((5/3)_n(2)_n) .

Cited by

• Proof of the Density Threshold Conjecture for Pinwheel Scheduling

Related

• A Note on the Gessel Numbers
• On a conjecture of Ira Gessel
• Counting Lattice Paths By Gessel Pairs
• Koroljuk's formula for counting lattice paths revisited
• A human proof for a generalization of Shalosh B. Ekhad's 10ⁿ Lattice Paths Theorem