A151379 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, 0), (1, -1), (1, 1)}.

1, 1, 4, 15, 84, 420, 2640, 15015, 100100, 612612, 4232592, 27159132, 192203088, 1274816400, 9178678080, 62386327575, 455053212900, 3151664844900, 23222793594000, 163256238965820, 1212760632317520, 8629643838226320, 64534727833692480, 463843356304664700, 3488102039411078544

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..500

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

Formula

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

From Benedict W. J. Irwin, Oct 14 2016: (Start)

a(n) = Catalan(n) * binomial(n, floor(n/2)).

G.f.: 3F2(1/4,1/2,3/4; 1,3/2; 64*x^2] + (1 - 2F1(-1/4,1/4; 1; 64*x^2))/(4*x). (End)

D-finite with recurrence n*(n+1)^2*a(n) -4*n*(2*n-1)*a(n-1) -16*(n-1)*(2*n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Feb 08 2021

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[0, k, 2 n], {k, 0, 2 n}], {n, 0, 25}]
Table[CatalanNumber[n]*Binomial[n, Floor[n/2]], {n, 0, 25}] (* G. C. Greubel, Oct 18 2016 *)

Prog

(PARI) a(n)=binomial(2*n, n) * binomial(n, n\2) / (n+1) \\ Charles R Greathouse IV, Oct 18 2016

Crossrefs

Cf. A000108, A001405.

Sequence in context: A081722 A117927 A143340 * A130679 A243048 A375633

Adjacent sequences: A151376 A151377 A151378 * A151380 A151381 A151382

Keyword

nonn,walk

Author

Manuel Kauers, Nov 18 2008

Status

approved