login
A151375
Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0), ending on the vertical axis and consisting of n steps taken from {(-1, -1), (0, 1), (1, -1)}.
1
1, 1, 1, 1, 3, 6, 10, 15, 49, 112, 216, 375, 1265, 3069, 6357, 11921, 40845, 102528, 221680, 436203, 1507593, 3869027, 8609811, 17511879, 60844223, 158598846, 360334950, 750899305, 2617859439, 6903200862, 15932387546, 33824479875, 118192674861, 314468570516, 734790352692, 1583113929243, 5540670299185
OFFSET
0,5
LINKS
M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008.
FORMULA
Recurrence: (n+1)*(n+3)*(n+4)*(119*n^5 - 100*n^4 - 2773*n^3 + 4990*n^2 + 1928*n - 1440)*a(n) = (238*n^8 + 1347*n^7 - 6631*n^6 - 27925*n^5 + 36265*n^4 + 93250*n^3 - 28096*n^2 - 63168*n - 17280)*a(n-1) + (357*n^8 + 1485*n^7 - 5949*n^6 - 4409*n^5 - 17576*n^4 + 33116*n^3 + 50288*n^2 + 113280*n + 59328)*a(n-2) - 16*(238*n^5 + 5899*n^4 - 33520*n^3 + 28955*n^2 + 22452*n - 8964)*a(n-3) + 64*(n-3)*(119*n^7 - 219*n^6 - 3625*n^5 + 8801*n^4 + 14131*n^3 - 41633*n^2 + 6766*n + 21120)*a(n-4) - 64*(n-4)*(n-3)*(238*n^6 + 157*n^5 - 8130*n^4 + 9636*n^3 + 23951*n^2 - 16996*n - 14676)*a(n-5) - 192*(n-5)*(n-4)*(n-3)*(119*n^5 + 495*n^4 - 1983*n^3 - 2739*n^2 + 3784*n + 2724)*a(n-6). - Vaclav Kotesovec, Aug 23 2014
a(n) ~ (36 + 27*sqrt(2) + 2*sqrt(2)*cos(Pi*n/2) + (27*sqrt(2)-36)*(-1)^n + 8*sin(Pi*n/2)) * 2^(3*n/2+3) / (9*Pi*n^3). - Vaclav Kotesovec, Aug 23 2014
G.f.: (1-2*x-3*x^2)^(1/2)*(2*x-1)*Int(x*(1+hypergeom([-1/4, 1/4],[1],64*x^4)/(2*x-1)+x*(8*x^2+x-1)*hypergeom([1/4, 3/4],[2],64*x^4)/(2*x-1)^2)/(1-2*x-3*x^2)^(3/2),x)/x^3. - Mark van Hoeij, Aug 25 2014
MAPLE
b:= proc(n, x, y) option remember; `if` (n<0 or x<0 or y<0 or n<x, 0, `if` (n=0, `if` (x=0, 1, 0), add (b(n-1, x+d[1], y+d[2]), d=[[-1, -1], [0, 1], [1, -1]]))) end: a:= n-> b(n, 0, 0):
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[i, -1 + j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[0, k, n], {k, 0, n}], {n, 0, 25}]
CROSSREFS
Sequence in context: A214282 A130200 A202269 * A353217 A310082 A153453
KEYWORD
nonn,walk
AUTHOR
Manuel Kauers, Nov 18 2008
STATUS
approved