A347947 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.

1, 3, 5, 24, 81, 298, 1070, 3868, 13960, 50417, 182084, 657707, 2375894, 8583264, 31009890, 112038032, 404803299, 1462624643, 5284813128, 19095564020, 68998567080, 249316670981, 900876831495, 3255230444720, 11762504284218, 42502963168784, 153581776819904

Offset

0,2

Comments

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..1000

Alois P. Heinz, Animation of a(5) = 298 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, v) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
      add(i^2, i=h)<add(i^2, i=l) and add(i^2, i=v-h)>add(i^2, i=v-l)
      , b(h, v), 0))(l+x), x=s(n))))(nops(l))
    end:
a:= n-> b([n, 1]$2):
seq(a(n), n=0..30);

Mathematica

s[n_] := s[n] = If[n == 0, {{}}, Sequence @@
     Table[Append[#, i], {i, -1, 1}]& /@ s[n-1]];
b[l_, v_] := b[l, v] = With[{n = Length[l]},
     If[l == Table[0, {n}], 1, Sum[With[{h = l + x},
     If[h.h<l.l && (v-h).(v-h)>(v-l).(v-l), b[h, v], 0]], {x, s[n]}]]];
a[n_] := b[{n, 1}, {n, 1}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 04 2021, after Alois P. Heinz *)

Crossrefs

Column (or row) k=1 of A346540.

Sequence in context: A230985 A286427 A290509 * A208800 A356274 A249935

Adjacent sequences: A347944 A347945 A347946 * A347948 A347949 A347950

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 20 2021

Status

approved