×

Proof of Ira Gessel’s lattice path conjecture. (English) Zbl 1203.05010

Summary: 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\geq 0\), \(y\geq 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}}\), where \((a)_n := a(a+1)\cdots(a+n-1)\).

MSC:

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

Software:

OEIS; DEtools
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Kreweras G (1965) Sur une classe de problmes lis au treillis des partitions d’entiers. Cah BURO 6:5â105.
[2] DOI: 10.1016/S0012-365X(00)00147-3 · Zbl 0963.05005 · doi:10.1016/S0012-365X(00)00147-3
[3] Mishna M (2007) Classifying lattice walks restricted to the quarter plane. Proceedings of the Nineteenth International Conference on Formal Power Series and Algebraic Combinatorics, (FPSAC), Tianjin, China, arXiv:math/0611651v1. · Zbl 1183.05004
[4] Sloane NJA The On-Line Encyclopedia of Integer Sequences, http://research.att.com/ njas/sequences/.
[5] PetkovÅ!ek M Wilf HS (2008) On a conjecture of Gessel. arXiv:0807.3203[math.CO].
[6] Bousquet-Mélou M Mishna M (2008) Walks with small steps in the quarter plane. arXiv:0810.4387 [math.CO].
[7] DOI: 10.1080/10236190802332084 · Zbl 1193.05014 · doi:10.1080/10236190802332084
[8] DOI: 10.1016/0377-0427(90)90042-X · Zbl 0738.33001 · doi:10.1016/0377-0427(90)90042-X
[9] Almkvist G Zeilberger D (1990) The method of differentiating under the integral sign. J Symb Comput 11(6):571â591. · Zbl 0717.33004 · doi:10.1016/S0747-7171(08)80159-9
[10] Takayama N (1990) An algorithm of constructing the integral of a module. Proceedings of ISSAC’90, 206â211.
[11] Takayama N (1990) Grbner basis, integration and transcendental functions. Proceedings of ISSAC’90, 152â156.
[12] DOI: 10.1006/jsco.1998.0207 · Zbl 0944.05006 · doi:10.1006/jsco.1998.0207
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.