OFFSET
0,4
COMMENTS
Lattice points may have negative coordinates, and different walks may differ in length. All walks are self-avoiding.
LINKS
Alois P. Heinz, Antidiagonals n = 0..140, flattened
Alois P. Heinz, Animation of A(2,4) = 173 walks
Wikipedia, Counting lattice paths
Wikipedia, Self-avoiding walk
FORMULA
A(n,k) = A(k,n).
EXAMPLE
Square array A(n,k) begins:
1, 1, 3, 7, 19, 51, 141, 393, ...
1, 3, 5, 24, 81, 298, 1070, 3868, ...
3, 5, 13, 25, 173, 739, 3423, 15363, ...
7, 24, 25, 63, 129, 1210, 6273, 34318, ...
19, 81, 173, 129, 321, 681, 8371, 51727, ...
51, 298, 739, 1210, 681, 1683, 3653, 57644, ...
141, 1070, 3423, 6273, 8371, 3653, 8989, 19825, ...
393, 3868, 15363, 34318, 51727, 57644, 19825, 48639, ...
...
MAPLE
s:= proc(n) option remember;
`if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
end:
b:= proc(l, v) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
add(i^2, i=h)<add(i^2, i=l) and add(i^2, i=v-h)>add(i^2, i=v-l)
, b(h, v), 0))(l+x), x=s(n))))(nops(l))
end:
A:= (n, k)-> b(sort([n, k])$2):
seq(seq(A(n, d-n), n=0..d), d=0..12);
MATHEMATICA
s[n_] := s[n] = If[n == 0, {{}}, Sequence @@
Table[Append[#, i], {i, -1, 1}]& /@ s[n-1]];
b[l_, v_] := b[l, v] = With[{n = Length[l]},
If[l == Table[0, {n}], 1, Sum[With[{h = l+x},
If[h.h<l.l && (v-h).(v-h)>(v-l).(v-l), b[h, v], 0]], {x, s[n]}]]];
A[n_, k_] := b[Sort[{n, k}], Sort[{n, k}]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Nov 04 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
AUTHOR
Alois P. Heinz, Sep 16 2021
STATUS
approved