cp's OEIS Frontend

A135404 Gessel sequence: the number of paths of length 2m in the plane, starting and ending at (0,1), with unit steps in the four directions (north, east, south, west) and staying in the region y > 0, x > -y.

%I A135404 #74 Jun 15 2023 17:01:31
%S A135404 1,2,11,85,782,8004,88044,1020162,12294260,152787976,1946310467,
%T A135404 25302036071,334560525538,4488007049900,60955295750460,
%U A135404 836838395382645,11597595644244186,162074575606984788,2281839419729917410,32340239369121304038,461109219391987625316,6610306991283738684600
%N A135404 Gessel sequence: the number of paths of length 2m in the plane, starting and ending at (0,1), with unit steps in the four directions (north, east, south, west) and staying in the region y > 0, x > -y.
%C A135404 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)}
%C A135404 According to Ira Gessel's student, Guoce Xin, Ira Gessel made his intriguing conjecture in 2001.
%C A135404 On June 25, 2008, the Gessel Conjecture became the Kauers-Koutschan-Zeilberger theorem - see the link. - _Doron Zeilberger_, Jul 01 2008
%D A135404 I. Gessel, private communication.
%H A135404 T. D. Noe, <a href="/A135404/b135404.txt">Table of n, a(n) for n = 0..200</a>
%H A135404 Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2023/30.pdf">From Kreweras to Gessel: A walk through patterns in the quarter plane</a>, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.
%H A135404 A. Ayyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ayyer/ayyer7.html">Towards a Human Proof of Gessel's Conjecture</a>, JIS 12 (2009) 09.4.2.
%H A135404 Alin Bostan and Manuel Kauers; with an appendix by Mark van Hoeij, <a href="http://dx.doi.org/10.1090/S0002-9939-2010-10398-2">The complete generating function for Gessel walks is algebraic</a>, Proc. Amer. Math. Soc. 138 (2010), 3063-3078.
%H A135404 M. Bousquet-Mélou and M. Mishna, <a href="http://arxiv.org/abs/0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008-2009.
%H A135404 Mireille Bousquet-Mélou, <a href="http://arxiv.org/abs/1503.08573">An elementary solution of Gessel's walks in the quadrant</a>, arXiv:1503.08573 [math.CO], 2015.
%H A135404 Timothy Budd, <a href="https://arxiv.org/abs/1709.04042">Winding of simple walks on the square lattice</a>, arXiv:1709.04042 [math.CO], 2017.
%H A135404 S. Garrabrant, I. Pak, <a href="http://arxiv.org/abs/1407.8222">Counting with irrational tiles</a>, arXiv:1407.8222 [math.CO], 2014.
%H A135404 Manuel Kauers, Christoph Koutschan and Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gessel.html">Proof of Ira Gessel's Lattice Path Conjecture</a>; <a href="/A135404/a135404.pdf">Local copy</a> [Pdf file only, no active links]
%H A135404 M. Kauers and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/quasiholo.html">The Quasi-Holonomic Ansatz and Restricted Lattice Walks</a>. J. Difference Equ. Appl. 14 (2008), no. 10-11, 1119-1126; <a href="/A135404/a135404_1.pdf">Local copy of Zeilberger's Introduction</a> [Pdf file only, no active links]
%H A135404 Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, <a href="https://arxiv.org/abs/2103.04599">A decomposition of ballot permutations, pattern avoidance and Gessel walks</a>, arXiv:2103.04599 [math.CO], 2021.
%F A135404 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).
%F A135404 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
%F A135404 G.f.: (1/(2*x)) * (hypergeom([ -1/2, -1/6], [2/3], 16 * x)-1). - _Mark van Hoeij_, Nov 02 2009
%F A135404 G.f.: hypergeom([1/2, 5/6, 1], [5/3, 2], 16*x). - _Mark van Hoeij_, Nov 02 2009
%F A135404 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
%F A135404 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
%F A135404 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
%F A135404 a(n) ~ 2^(2/3)*GAMMA(1/3)/(3*Pi) * 16^n/n^(7/3). - _Vaclav Kotesovec_, Aug 11 2013
%F A135404 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
%e A135404 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.
%e A135404 G.f. = 1 + 2*x + 11*x^2 + 85*x^3 + 782*x^4 + 8004*x^5 + 1020162*x^6 + ...
%p A135404 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}.
%p A135404 # Maple code from _N. J. A. Sloane_, Mar 31 2015:
%p A135404 rf:=proc(a,n) mul(a+i,i=0..n-1); end;
%p A135404 f:=n->16^n*rf(5/6,n)*rf(1/2,n)/(rf(5/3,n)*rf(2,n));
%p A135404 [seq(f(n),n=0..50)];
%t A135404 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}]
%t A135404 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 *)
%t A135404 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 *)
%Y A135404 Cf. A060900 (gives the total number of walks, regardless of final destination).
%K A135404 nonn,walk
%O A135404 0,2
%A A135404 _Doron Zeilberger_, Dec 11 2007
%E A135404 More terms from _Manuel Kauers_, Nov 18 2008
%E A135404 Edited by _N. J. A. Sloane_, Aug 28 2010