|
%I #18 Nov 04 2021 11:08:48
%S 1,3,5,24,81,298,1070,3868,13960,50417,182084,657707,2375894,8583264,
%T 31009890,112038032,404803299,1462624643,5284813128,19095564020,
%U 68998567080,249316670981,900876831495,3255230444720,11762504284218,42502963168784,153581776819904
%N Number of walks on square lattice from (1,n) to (0,0) using steps that decrease the Euclidean distance to the origin and increase the Euclidean distance to (n,1) and that change each coordinate by at most 1.
%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="/A347947/b347947.txt">Table of n, a(n) for n = 0..1000</a>
%H Alois P. Heinz, <a href="/A347947/a347947.gif">Animation of a(5) = 298 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, v) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
%p add(i^2, i=h)<add(i^2, i=l) and add(i^2, i=v-h)>add(i^2, i=v-l)
%p , b(h, v), 0))(l+x), x=s(n))))(nops(l))
%p end:
%p a:= n-> b([n, 1]$2):
%p seq(a(n), n=0..30);
%t s[n_] := s[n] = If[n == 0, {{}}, Sequence @@
%t Table[Append[#, i], {i, -1, 1}]& /@ s[n-1]];
%t b[l_, v_] := b[l, v] = With[{n = Length[l]},
%t If[l == Table[0, {n}], 1, Sum[With[{h = l + x},
%t If[h.h<l.l && (v-h).(v-h)>(v-l).(v-l), b[h, v], 0]], {x, s[n]}]]];
%t a[n_] := b[{n, 1}, {n, 1}];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 04 2021, after _Alois P. Heinz_ *)
%Y Column (or row) k=1 of A346540.
%K nonn,walk
%O 0,2
%A _Alois P. Heinz_, Sep 20 2021
|
