A346541 Number of walks on square lattice from (n,2n) to (0,0) using steps that decrease the Euclidean distance to the origin and increase the Euclidean distance to (n,2n) and that change each coordinate by at most 1.

1, 5, 173, 6273, 327304, 19662204, 1331125733, 97103842536, 7486548949630, 600824064355643, 49716537270181030, 4212436222856773156, 363673201239600512658, 31874623637580787947172, 2828388650238276648013964, 253555200931317108300020394, 22925898959060646660438636660

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

Alois P. Heinz, Animation of a(2) = 173 walks

Wikipedia, Counting lattice paths

Wikipedia, Self-avoiding walk

Formula

a(n) = A346540(2n,n) = A346540(n,2n).

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, 2*n]$2):
seq(a(n), n=0..20);

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, 2n}, {n, 2n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 04 2021, after Alois P. Heinz *)

Crossrefs

Cf. A346540.

Sequence in context: A139986 A354573 A123111 * A380628 A303154 A060070

Adjacent sequences: A346538 A346539 A346540 * A346542 A346543 A346544

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 16 2021

Status

approved