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.

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

Author

Alois P. Heinz, Sep 14 2021

Keywords

• nonn
• walk

Comments

All terms are odd.

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..1236
• Alois P. Heinz, Animation of a(4) = 173 walks
• Wikipedia, Counting lattice paths
• Wikipedia, Self-avoiding walk

Crossrefs

Column (or row) k=0 of A346538.

Cf. A002426.

Programs

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) 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 *)