|
|
A060900
|
|
Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.
|
|
7
|
|
|
1, 2, 7, 21, 78, 260, 988, 3458, 13300, 47880, 185535, 680295, 2649570, 9841260, 38470380, 144263925, 565514586, 2136388436, 8392954570, 31893227366, 125515281892, 479240167224, 1888770070824, 7240285271492, 28569774314536, 109883747363600, 434040802086220
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017; https://specfun.inria.fr/bostan/HDR.pdf
|
|
LINKS
|
|
|
FORMULA
|
The following conjectural formula for this sequence is apparently due to Ira M. Gessel: a(0) = 1, a(2n) = a(2n-1)*(12n+2)/(3n+1), a(2n+1) = a(2n)*(4n+2)/(n+1).
G.f.: (hypergeom([ -1/12, 1/4],[2/3],-64*x*(4*x+1)^2/(4*x-1)^4)-1)/(2*x). - Mark van Hoeij, Nov 02 2009
G.f.: (T(x)-1)/(2*x) where T(x) satisfies 27*(4*x-1)^2*T^8 - 18*(4*x-1)^2*T^4 - (128*x^2+192*x+8)*T^2 - (4*x-1)^2 = 0. - Mark van Hoeij, Nov 02 2009
a(n) ~ 4^(n+1) / (sqrt(3) * Gamma(1/3) * n^(2/3)). - Vaclav Kotesovec, Sep 17 2017
|
|
MAPLE
|
b:= proc(n, x, y) option remember;
`if`(x<0 or y>x, 0, `if`(n=0, 1, add(add(
b(n-1, x+i, y+j), j=[-1, 1]), i=[-1, 1])))
end:
a:= n-> b(n, 0$2):
|
|
MATHEMATICA
|
(* Conjectural *) a[0]=1; a[n_] := a[n] = If[EvenQ[n], (4*(3*n+1)*a[n-1])/ (3*n+2), (4*n*a[n-1])/(n+1)]; Table[a[n], {n, 0, 26}]
(* or, from 1st g.f. *) s = (HypergeometricPFQ[{-1/12, 1/4}, {2/3}, -64*x* (4*x+1)^2/(4*x-1)^4]-1)/(2*x) + O[x]^27; CoefficientList[s, x](* Jean-François Alcover, Nov 30 2015 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|