cp's OEIS Frontend

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.

%I A347814 #16 Nov 03 2021 08:34:01
%S A347814 1,1,7,29,173,937,5527,32309,193663,1166083,7093413,43373465,
%T A347814 266712433,1646754449,10205571945,63442201565,395457341485,
%U A347814 2470816812547,15469821698211,97035271087123,609662167537831,3836108862182671,24169777826484697,152468665277411533
%N 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.
%C A347814 All terms are odd.
%C A347814 Lattice points may have negative coordinates, and different walks may differ in length.  All walks are self-avoiding.
%H A347814 Alois P. Heinz, <a href="/A347814/b347814.txt">Table of n, a(n) for n = 0..1236</a>
%H A347814 Alois P. Heinz, <a href="/A347814/a347814.gif">Animation of a(4) = 173 walks</a>
%H A347814 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%H A347814 Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-avoiding_walk">Self-avoiding walk</a>
%p A347814 s:= proc(n) option remember;
%p A347814      `if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
%p A347814     end:
%p A347814 b:= proc(l) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
%p A347814       add(i^2, i=h)<add(i^2, i=l), b(sort(h)), 0))(l+x), x=s(n))))(nops(l))
%p A347814     end:
%p A347814 a:= n-> b([0, n]):
%p A347814 seq(a(n), n=0..30);
%t A347814 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 A347814 a[n_] := b[0, n];
%t A347814 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 03 2021, after _Alois P. Heinz_ *)
%Y A347814 Column (or row) k=0 of A346538.
%Y A347814 Cf. A002426.
%K A347814 nonn,walk
%O A347814 0,3
%A A347814 _Alois P. Heinz_, Sep 14 2021