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

1, 2, 28, 660, 20020, 705432, 27457584, 1147334760, 50561468100, 2322279359400, 110250966574320, 5377893986141040, 268315541493159888, 13645106597301720800, 705378072079232798400, 36985702814877062972880, 1963555139681260758978660, 105393959626252993455319560

Offset

0,2

Comments

a(n) is also the number of words of 4n length consisting of 2n X's, n Y's and n Z's such that any initial segment of the string has at least as many X's as Y+Z's, and at least as many Y's as Z's. - Istvan Marosi, Apr 27 2014

Links

Alois P. Heinz, Table of n, a(n) for n = 0..558

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

Formula

a(n) = A000108(n)*A000108(2n). - Istvan Marosi, Apr 27 2014

a(n) = A056040(4*n)*A056040(2*n)/A000384(n+1). - Peter Luschny, Apr 28 2014

G.f.: hypergeom([1/4, 1/2, 3/4], [3/2, 2], 64*x). - Robert Israel, Aug 14 2014

D-finite with recurrence n*(n+1)*(2*n+1)*a(n) - 4*(4*n-3)*(2*n-1)*(4*n-1)*a(n-1) = 0. - R. J. Mathar, Jul 27 2022

a(n) ~ 2^(6*n-3/2) / (n^3 * Pi). - Amiram Eldar, Oct 06 2025

Maple

a:= proc(n) option remember; `if`(n=0, 1,
      (4*(4*n-3)*(2*n-1)*(4*n-1)*a(n-1))/(n*(n+1)*(2*n+1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 27 2014
# Alternative:
S := proc(a) global x; series(a, x=0, 20) end:
ogf := S(int(S(x^(-1/2)*hypergeom([1/4, 3/4], [2], 64*x)), x)/(2*x^(1/2))):
gfun[seriestolist](%)[];  # Mark van Hoeij, Aug 14 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[aux[0, 0, 4 n], {n, 0, 25}]

Crossrefs

Cf. A000108, A000384, A056040.

Sequence in context: A373315 A246483 A384163 * A098631 A089836 A372164

Adjacent sequences: A151329 A151330 A151331 * A151333 A151334 A151335

Keyword

nonn,walk,easy

Author

Manuel Kauers, Nov 18 2008

Status

approved