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

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

Offset: 0

Author

David W. Wilson, May 05 2001

Keywords

• nonn

References

• 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

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• A. Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.
• A. Bostan, Computer Algebra for Lattice Path Combinatorics, 7th Séminaire Lotharingien de Combinatoire, Ellwangen, March 23-25, 2015.

Crossrefs

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

Programs

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):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 30 2015

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 *)

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

Extensions

Entry revised by N. J. A. Sloane at the suggestion of Doron Zeilberger, Sep 13 2007