A347814 - OEIS

%I #16 Nov 03 2021 08:34:01

%S 1,1,7,29,173,937,5527,32309,193663,1166083,7093413,43373465,

%T 266712433,1646754449,10205571945,63442201565,395457341485,

%U 2470816812547,15469821698211,97035271087123,609662167537831,3836108862182671,24169777826484697,152468665277411533

%N 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.

%C All terms are odd.

%C Lattice points may have negative coordinates, and different walks may differ in length.  All walks are self-avoiding.

%H Alois P. Heinz, <a href="/A347814/b347814.txt">Table of n, a(n) for n = 0..1236</a>

%H Alois P. Heinz, <a href="/A347814/a347814.gif">Animation of a(4) = 173 walks</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-avoiding_walk">Self-avoiding walk</a>

%p s:= proc(n) option remember;

%p      `if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))

%p     end:

%p b:= proc(l) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(

%p       add(i^2, i=h)<add(i^2, i=l), b(sort(h)), 0))(l+x), x=s(n))))(nops(l))

%p     end:

%p a:= n-> b([0, n]):

%p seq(a(n), n=0..30);

%t 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}]];

%t a[n_] := b[0, n];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 03 2021, after _Alois P. Heinz_ *)

%Y Column (or row) k=0 of A346538.

%Y Cf. A002426.

%K nonn,walk

%O 0,3

%A _Alois P. Heinz_, Sep 14 2021