|
| |
|
|
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.
|
|
6
|
|
|
|
1, 2, 11, 85, 782, 8004, 88044, 1020162, 12294260, 152787976, 1946310467, 25302036071, 334560525538, 4488007049900, 60955295750460, 836838395382645, 11597595644244186, 162074575606984788, 2281839419729917410, 32340239369121304038, 461109219391987625316, 6610306991283738684600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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}.
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
|
Cf. A060900 (gives the total number of walks, regardless of final destination).
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
