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

Author

Manuel Kauers, Nov 18 2008

Keywords

• nonn
• walk

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
• M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008.

Programs

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
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)));  # 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}]

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