cp's OEIS Frontend

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

%I A060900 #37 Jun 27 2025 23:16:43
%S A060900 1,2,7,21,78,260,988,3458,13300,47880,185535,680295,2649570,9841260,
%T A060900 38470380,144263925,565514586,2136388436,8392954570,31893227366,
%U A060900 125515281892,479240167224,1888770070824,7240285271492,28569774314536,109883747363600,434040802086220
%N A060900 Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.
%D A060900 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 A060900 Alois P. Heinz, <a href="/A060900/b060900.txt">Table of n, a(n) for n = 0..500</a>
%H A060900 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 A060900 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 A060900 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 A060900 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 A060900 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 A060900 a(n) ~ 4^(n+1) / (sqrt(3) * Gamma(1/3) * n^(2/3)). - _Vaclav Kotesovec_, Sep 17 2017
%p A060900 b:= proc(n, x, y) option remember;
%p A060900       `if`(x<0 or y>x, 0, `if`(n=0, 1, add(add(
%p A060900        b(n-1, x+i, y+j), j=[-1, 1]), i=[-1, 1])))
%p A060900     end:
%p A060900 a:= n-> b(n, 0$2):
%p A060900 seq(a(n), n=0..30);  # _Alois P. Heinz_, Nov 30 2015
%t A060900 (* 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 A060900 (* 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 A060900 Cf. A005566, A001700, A060897, A060898, A060899.
%K A060900 nonn
%O A060900 0,2
%A A060900 _David W. Wilson_, May 05 2001
%E A060900 Entry revised by _N. J. A. Sloane_ at the suggestion of _Doron Zeilberger_, Sep 13 2007