A151255 Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, -1), (-1, 1), (1, 0)}

1, 1, 2, 3, 8, 15, 39, 77, 216, 459, 1265, 2739, 7842, 17641, 49854, 113175, 327604, 761787, 2182833, 5101595, 14868582, 35338401, 102146176, 243510453, 713019480, 1721265625, 5005198029, 12105626337, 35565979706, 86870058279, 253706973975, 620415879229, 1827423157812, 4504531840875, 13199126952109

Offset

0,3

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

Table of n, a(n) for n=0..34.

A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

A. Bostan and M. Kauers, 2008. Automatic Classification of Restricted Lattice Walks, ArXiv 0811.2899.

M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.

Formula

G.f. (1-2*x)*(1-((1-3*x)*(1+x))^(1/2)*(1-Int((2*(1-6*x^2-8*x^3)*hypergeom([1/4, 3/4],[1],64*x^4)+8*x^3*(1-7*x+4*x^2)*hypergeom([3/4, 5/4],[2],64*x^4))/((1-2*x)^2*((1-3*x)*(1+x))^(1/2)*(1+x)),x))/(1-3*x))/(4*x^2). - Mark van Hoeij, Aug 16 2014

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, j, -1 + n] + aux[1 + i, -1 + j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[i, j, n], {i, 0, n}, {j, 0, n}], {n, 0, 25}]

Crossrefs

Sequence in context: A055543 A308433 A049957 * A147999 A148000 A148001

Adjacent sequences: A151252 A151253 A151254 * A151256 A151257 A151258

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved