OFFSET
0,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..223
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk
FORMULA
Recurrence: (768*n^7 - 9760*n^6 + 42960*n^5 - 72624*n^4 + 4272*n^3 + 120634*n^2 - 117042*n + 29523)*a(n) = 4*(1536*n^9 - 17216*n^8 + 56928*n^7 - 19536*n^6 - 199576*n^5 + 257144*n^4 + 67826*n^3 - 200220*n^2 + 46970*n - 201)*a(n-1) - (12288*n^11 - 143872*n^10 + 517376*n^9 - 304896*n^8 - 1803648*n^7 + 3174144*n^6 - 434416*n^5 - 1420224*n^4 - 672608*n^3 + 1216378*n^2 - 69926*n - 51561)*a(n-2) + 8*(n-1)*(3072*n^10 - 40576*n^9 + 179200*n^8 - 212640*n^7 - 583984*n^6 + 1881504*n^5 - 1496616*n^4 - 314158*n^3 + 703776*n^2 - 93829*n - 15912)*a(n-3) - 4*(n-2)*(n-1)*(2*n - 9)*(2*n - 7)*(768*n^7 - 4384*n^6 + 528*n^5 + 22656*n^4 - 24944*n^3 - 2966*n^2 + 8162*n - 1269)*a(n-4). - Vaclav Kotesovec, Apr 25 2017
a(n) ~ c * n^(2*n+4) * 2^(2*n) / exp(2*n), where c = 2.064339567965... - Vaclav Kotesovec, Apr 25 2017
MAPLE
b:= proc(x, y, t) option remember;
`if`(x<0 or y<0, 0,
`if`(x=0 and y=0, [1$2], (p-> p+[0, p[1]])(
`if`(x>y, b(x-1, y, 0), 0)+
`if`(y>x, b(x, y-1, 0), 0)+
b(x-1, y-1, 0)+
`if`(t<>2, b(x+1, y-1, 1), 0)+
`if`(t<>1, b(x-1, y+1, 2), 0))))
end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..20);
MATHEMATICA
b[x_, y_, t_] := b[x, y, t] = If[x < 0 || y < 0, 0, If[x == 0 && y == 0, {1, 1}, Function[p, p + {0, p[[1]]}][If[x > y, b[x - 1, y, 0], 0] + If[y > x, b[x, y - 1, 0], 0] + b[x - 1, y - 1, 0] + If[t != 2, b[x + 1, y - 1, 1], 0] + If[t != 1, b[x - 1, y + 1, 2], 0]]]];
a[n_] := b[n, n, 0][[2]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 19 2017, translated from Maple *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Alois P. Heinz, Apr 24 2017
STATUS
approved