OFFSET
0,2
COMMENTS
An equivalent definition: number of walks within N^2 (the first quadrant of Z^2) starting and ending at (0,0) and consisting of 2 n steps taken from {(-1, -1), (-1, 0), (1, 0), (1, 1)}
According to Ira Gessel's student, Guoce Xin, Ira Gessel made his intriguing conjecture in 2001.
On June 25, 2008, the Gessel Conjecture became the Kauers-Koutschan-Zeilberger theorem - see the link. - Doron Zeilberger, Jul 01 2008
REFERENCES
I. Gessel, private communication.
LINKS
T. D. Noe, Table of n, a(n) for n = 0..200
Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, From Kreweras to Gessel: A walk through patterns in the quarter plane, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.
A. Ayyer, Towards a Human Proof of Gessel's Conjecture, JIS 12 (2009) 09.4.2.
Alin Bostan and Manuel Kauers; with an appendix by Mark van Hoeij, The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc. 138 (2010), 3063-3078.
M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
Mireille Bousquet-Mélou, An elementary solution of Gessel's walks in the quadrant, arXiv:1503.08573 [math.CO], 2015.
Timothy Budd, Winding of simple walks on the square lattice, arXiv:1709.04042 [math.CO], 2017.
S. Garrabrant, I. Pak, Counting with irrational tiles, arXiv:1407.8222 [math.CO], 2014.
Manuel Kauers, Christoph Koutschan and Doron Zeilberger, Proof of Ira Gessel's Lattice Path Conjecture; Local copy [Pdf file only, no active links]
M. Kauers and D. Zeilberger, The Quasi-Holonomic Ansatz and Restricted Lattice Walks. J. Difference Equ. Appl. 14 (2008), no. 10-11, 1119-1126; Local copy of Zeilberger's Introduction [Pdf file only, no active links]
Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, A decomposition of ballot permutations, pattern avoidance and Gessel walks, arXiv:2103.04599 [math.CO], 2021.
FORMULA
The Ira Gessel Conjecture is that a(m)=16^m*(5/6)_m*(1/2)_m/ ((2)_m*(5/3)_m), where (a)_m:=a*(a+1)*...*(a+m-1).
This sequence is given by the simple recurrence: a(0) = 1; (10+11*n+3*n^2)*a(n+1) = (20+64*n+48*n^2)*a(n). - Iwan Jensen (I.Jensen(AT)ms.unimelb.edu.au), Jul 01 2008
G.f.: (1/(2*x)) * (hypergeom([ -1/2, -1/6], [2/3], 16 * x)-1). - Mark van Hoeij, Nov 02 2009
G.f.: hypergeom([1/2, 5/6, 1], [5/3, 2], 16*x). - Mark van Hoeij, Nov 02 2009
G.f.: (T(x)-1)/(2*x) where T(x) satisfies 27*T^8-18*(1+256*x^2+224*x)*T^4-8*(16*x+1)*(256*x^2-544*x+1)*T^2-(1+256*x^2+224*x)^2 = 0. - Mark van Hoeij, Nov 02 2009
G.f.: (1/(8*x)) * (27*T^7-21*T^3+(256*x-2)*T-4) where T satisfies 27*T^8-18*T^4+(-8+256*x)*T^2-1 = 0, T(0)=1. - Mark van Hoeij, Nov 02 2009
G.f.: (T(x)-1)/(2*x) where T(x) satisfies T(x(1+x)^3/(1+4x)^3) = (1+8x+4x^2)/(1+4x)^(3/2). - Ira M. Gessel, Mar 06 2013
a(n) ~ 2^(2/3)*GAMMA(1/3)/(3*Pi) * 16^n/n^(7/3). - Vaclav Kotesovec, Aug 11 2013
a(n) = (2^(2/3+4*n) * Gamma(4/3) * Gamma(1/2+n) * Gamma(5/6+n)) / (Pi*Gamma(5/3+n) * Gamma(2+n)). - Benedict W. J. Irwin, Aug 10 2016
EXAMPLE
a(1)=2 since there are only two walks, starting and ending at (0,1), of length 2, that stay in y>0, x>-y, namely: NS, EW. The other two walks, SN, WE, venture outside the allowed region.
G.f. = 1 + 2*x + 11*x^2 + 85*x^3 + 782*x^4 + 8004*x^5 + 1020162*x^6 + ...
MAPLE
See the Maple package QuarterPlane in the webpage http://www.math.rutgers.edu/~zeilberg/tokhniot/QuarterPlane. See in particular Procedure W, which can handle any set of steps. Gessel's problem is equivalent to walks in the positive quarter-plane, starting and ending at the origin, with steps {E, W, NE, SW}.
# Maple code from N. J. A. Sloane, Mar 31 2015:
rf:=proc(a, n) mul(a+i, i=0..n-1); end;
f:=n->16^n*rf(5/6, n)*rf(1/2, n)/(rf(5/3, n)*rf(2, n));
[seq(f(n), n=0..50)];
MATHEMATICA
aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[-1 + i, j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[aux[0, 0, 2 n], {n, 0, 25}]
a[ n_] := If[ n<0, 0, 16^n Pochhammer[ 5/6, n] Pochhammer[ 1/2, n] / Pochhammer[ 5/3, n] / Pochhammer[2, n]] (* Michael Somos, Jun 30 2011 *)
FullSimplify[Table[(2^(2/3+4n)Gamma[4/3]Gamma[1/2+n]Gamma[5/6+n])/(Pi Gamma[5/3+n]Gamma[2+n]), {n, 0, 20}]] (* Benedict W. J. Irwin, Aug 10 2016 *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Doron Zeilberger, Dec 11 2007
EXTENSIONS
More terms from Manuel Kauers, Nov 18 2008
Edited by N. J. A. Sloane, Aug 28 2010
STATUS
approved