login
Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.
7

%I #35 Jun 25 2021 23:11:51

%S 1,2,7,21,78,260,988,3458,13300,47880,185535,680295,2649570,9841260,

%T 38470380,144263925,565514586,2136388436,8392954570,31893227366,

%U 125515281892,479240167224,1888770070824,7240285271492,28569774314536,109883747363600,434040802086220

%N Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.

%C 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

%H Alois P. Heinz, <a href="/A060900/b060900.txt">Table of n, a(n) for n = 0..500</a>

%H A. Bostan, <a href="https://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.

%H A. Bostan, <a href="http://www.emis.de/journals/SLC/wpapers/s74vortrag/bostan2.pdf">Computer Algebra for Lattice Path Combinatorics</a>, 7th Séminaire Lotharingien de Combinatoire, Ellwangen, March 23-25, 2015.

%F 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).

%F 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

%F 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

%F a(n) ~ 4^(n+1) / (sqrt(3) * Gamma(1/3) * n^(2/3)). - _Vaclav Kotesovec_, Sep 17 2017

%p b:= proc(n, x, y) option remember;

%p `if`(x<0 or y>x, 0, `if`(n=0, 1, add(add(

%p b(n-1, x+i, y+j), j=[-1, 1]), i=[-1, 1])))

%p end:

%p a:= n-> b(n, 0$2):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 30 2015

%t (* 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}]

%t (* 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 *)

%Y Cf. A005566, A001700, A060897, A060898, A060899.

%K nonn

%O 0,2

%A _David W. Wilson_, May 05 2001

%E Entry revised by _N. J. A. Sloane_ at the suggestion of _Doron Zeilberger_, Sep 13 2007