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,3

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

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

Adjacent sequences: A347811 A347812 A347813 * A347815 A347816 A347817

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 14 2021

Status

approved