OFFSET
0,2
COMMENTS
Lattice points may have negative coordinates, and different walks may differ in length. All walks are self-avoiding.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..201
Wikipedia, Counting lattice paths
Wikipedia, Self-avoiding walk
EXAMPLE
a(1) = 19:
((1,1,1), (0,0,0)),
((1,1,1), (0,0,1), (0,0,0)),
((1,1,1), (0,1,0), (0,0,0)),
((1,1,1), (0,1,1), (0,0,0)),
((1,1,1), (1,0,0), (0,0,0)),
((1,1,1), (1,0,1), (0,0,0)),
((1,1,1), (1,1,0), (0,0,0)),
((1,1,1), (0,1,1), (-1,0,0), (0,0,0)),
((1,1,1), (0,1,1), (0,0,1), (0,0,0)),
((1,1,1), (0,1,1), (0,1,0), (0,0,0)),
((1,1,1), (0,1,1), (1,0,0), (0,0,0)),
((1,1,1), (1,0,1), (0,-1,0), (0,0,0)),
((1,1,1), (1,0,1), (0,0,1), (0,0,0)),
((1,1,1), (1,0,1), (0,1,0), (0,0,0)),
((1,1,1), (1,0,1), (1,0,0), (0,0,0)),
((1,1,1), (1,1,0), (0,0,-1), (0,0,0)),
((1,1,1), (1,1,0), (0,0,1), (0,0,0)),
((1,1,1), (1,1,0), (0,1,0), (0,0,0)),
((1,1,1), (1,1,0), (1,0,0), (0,0,0)).
MAPLE
s:= proc(n) option remember;
`if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
end:
b:= proc(l) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
add(i^2, i=h)<add(i^2, i=l), b(sort(h)), 0))(l+x), x=s(n))))(nops(l))
end:
a:= n-> b([n$3]):
seq(a(n), n=0..12);
MATHEMATICA
s[n_] := s[n] = If[n == 0, {{}}, Sequence @@ Table[Append[#, i], {i, -1, 1}]& /@ s[n-1]];
b[l_List] := b[l] = With[{n = Length[l]}, If[l == Table[0, {n}], 1, Sum[With[{h = l+x}, If[h.h < l.l, b[Sort[h]], 0]], {x, s[n]}]]];
a[n_] := b[{n, n, n}];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Nov 04 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Alois P. Heinz, Sep 14 2021
STATUS
approved