0,2

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 (zeilberg(AT)math.rutgers.edu), Jul 01 2008

I. Gessel, private communication to certain people.

M. Kauers and D. Zeilberger, The Quasi-Holonomic Ansatz and Restricted Lattice Walks. To appear in J. for Difference Equations and Applications, special issue in honor of Gerry Ladas' 70th Birthday.

Manuel Kauers, Christoph Koutschan and Doron Zeilberger, Proof of Ira Gessel's Lattice Path Conjecture

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) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 02 2009]

G.f.: hypergeom([1/2, 5/6, 1], [5/3, 2], 16*x) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), 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 [From Mark van Hoeij (hoeij(AT)math.fsu.edu), 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 [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 02 2009]

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.

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} .

Cf. A060900 (gives the total number of walks, regardless of final destination) .

Sequence in context: A158098 A104185 A074604 this_sequence A151360 A153304 A036076

Adjacent sequences: A135401 A135402 A135403 this_sequence A135405 A135406 A135407

nonn

Doron Zeilberger (zeilberg(AT)math.rutgers.edu), Dec 11 2007