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

1, 3, 21, 193, 2034, 23283, 281688, 3545919, 45988056, 610459630, 8255756937, 113365682625, 1576636806694, 22164611973120, 314485620041700, 4498007052780945, 64786471166282742, 938935711652184576, 13682852009343599910, 200380515615362566026, 2947534319535871403052, 43531501857033753446055

Offset

0,2

Links

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

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

Formula

Recurrence: n*(n+1)*(3*n+1)*(3*n+2)*(4*n-3)*a(n) = 8*n*(2*n-1)*(4*n-1)*(18*n^2 - 9*n - 4)*a(n-1) - 16*(2*n-3)*(2*n-1)*(4*n+1)*(6*n-7)*(6*n-5)*a(n-2). - Vaclav Kotesovec, Aug 14 2013

a(n) ~ 2^(4*n+4/3)*GAMMA(2/3)/(3*Pi*n^(5/3)) * (1 + sqrt(3)*2^(1/3)*Pi/(9*GAMMA(2/3)^2*n^(2/3))). - Vaclav Kotesovec, Aug 14 2013

Maple

b:= proc(n, l) option remember; `if` (-1 in {l[]} or n<l[1], 0, `if`
      (n=0, 1, add (b(n-1, l+d), d=[[-1, -1], [-1, 0], [1, 0], [1, 1]])))
    end:
a:= n-> b(2*n, [0$2]):
seq (a(n), n=0..50);  # Alois P. Heinz, Jul 02 2011

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

Crossrefs

Sequence in context: A219535 A292361 A369783 * A210670 A193468 A132863

Adjacent sequences: A151385 A151386 A151387 * A151389 A151390 A151391

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved