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