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

1, 1, 3, 7, 19, 49, 139, 379, 1079, 3011, 8681, 24641, 71303, 204359, 594749, 1717871, 5012591, 14552407, 42601285, 124209955, 364300377, 1065449397, 3131483367, 9182889013, 27027421303, 79418096239, 234090990589, 689093244919, 2033346353509, 5994168369289, 17706646341619, 52264890828619

Offset

0,3

Links

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

M. Alekseyev, Count the number of words in a set, MathOverflow, 2018.

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

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.

Bostan, Alin ; Chyzak, Frédéric; van Hoeij, Mark; Kauers, Manuel; Pech, Lucien Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. Eur. J. Comb. 61, 242-275 (2017)

A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.

M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.

Formula

a(n) = Sum_{j=0..[n/2]} Sum_{i=max(j,[(n+1)/2]-j)..n-j} (i-j+1)*(2*(i+j)-n+1)/(i+j+1) * n!/(i+1)!/j!/(n-i-j)!. - Max Alekseyev, Mar 06 2018

G.f.: -(1/(x-1))*(1/2+1/x*Int(x^2/(x+1)^(1/2)/(1-3*x)^(3/2)*(13/2+Int(((1-3*x)/(x+1))^(1/2)*((10-1/x^3)*hypergeom([1/4, 3/4],[1],64*x^4)+6*(8*x^2+1)*(10*x^2-3)*hypergeom([5/4,7/4],[2],64*x^4)),x)),x)). - Mark van Hoeij, Oct 13 2009

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

Prog

(PARI) { A151266(n) = sum(j=0, n\2, sum(i=max(j, (n+1)\2-j), n-j, (i-j+1)*(2*(i+j)-n+1)/(i+j+1) * n!/(i+1)!/j!/(n-i-j)! )); } \\ Max Alekseyev, Mar 06 2018

Crossrefs

Sequence in context: A017927 A116903 A298416 * A147234 A171854 A182895

Adjacent sequences: A151263 A151264 A151265 * A151267 A151268 A151269

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved