login
A347814
Number of walks on square lattice from (n,0) to (0,0) using steps that decrease the Euclidean distance to the origin and that change each coordinate by at most 1.
2
1, 1, 7, 29, 173, 937, 5527, 32309, 193663, 1166083, 7093413, 43373465, 266712433, 1646754449, 10205571945, 63442201565, 395457341485, 2470816812547, 15469821698211, 97035271087123, 609662167537831, 3836108862182671, 24169777826484697, 152468665277411533
OFFSET
0,3
COMMENTS
All terms are odd.
Lattice points may have negative coordinates, and different walks may differ in length. All walks are self-avoiding.
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([0, n]):
seq(a(n), n=0..30);
MATHEMATICA
b[n_, k_] := b[n, k] = If[{n, k} == {0, 0}, 1, Sum[Sum[If[i^2 + j^2 < n^2 + k^2, b@@Sort[{i, j}], 0], {j, k-1, k+1}], {i, n-1, n+1}]];
a[n_] := b[0, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 03 2021, after Alois P. Heinz *)
CROSSREFS
Column (or row) k=0 of A346538.
Cf. A002426.
Sequence in context: A266473 A297677 A287860 * A175208 A307954 A071918
KEYWORD
nonn,walk
AUTHOR
Alois P. Heinz, Sep 14 2021
STATUS
approved