OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1280
Alois P. Heinz, Animation of a(5) = 369 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk
FORMULA
a(n) ~ sqrt(5 + 1/sqrt(13)) * (70 + 26*sqrt(13))^n / (2^(3/2) * sqrt(Pi*n) * 3^(3*n + 3/2)). - Vaclav Kotesovec, Oct 12 2019
From Peter Luschny, May 19 2021: (Start)
Next three formulas for n >= 1:
a(n) = A026300(2*n - 1, n - 1).
a(n) = Sum_{j=0..floor((n-1)/2)} C(2*n-1, 2*j + n)*(C(2*j + n, j) - C(2*j +n, j-1)).
a(n) = binomial(2*n - 1, n - 1)*hypergeom([(2 - n)/2, (1 - n)/2], [n + 2], 4). (End)
MAPLE
b:= proc(x, y, t) option remember; `if`(min(x, y)<0, 0,
`if`(max(x, y)=0, 1, b(x-1, y, 1)+
`if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);
MATHEMATICA
b[x_, y_, t_] := b[x, y, t] = If[Min[x, y] < 0, 0, If[Max[x, y]==0, 1, b[x - 1, y, 1] + If[t==1, b[x - 1, y + 1, 0] + b[x + 1, y - 1, 0], 0]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, May 13 2020, after Maple *)
a[n_] := Binomial[2n - 1, n - 1] Hypergeometric2F1[(2 - n)/2, (1 - n)/2, n + 2, 4];
a[0] := 1; Table[a[n], {n, 0, 24}] (* Peter Luschny, May 19 2021 *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Alois P. Heinz, Sep 28 2019
STATUS
approved