A347810 Number of n-dimensional lattice walks from {n}^n to {0}^n using steps that decrease the Euclidean distance to the origin and that change each coordinate by at most 1.

1, 1, 25, 2062017739, 255053951339165796439851848897794625

Offset: 0

Author

Alois P. Heinz, Sep 14 2021

Keywords

• nonn
• walk

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..6
• Alois P. Heinz, Animation of a(2) = 25 walks
• Wikipedia, Counting lattice paths
• Wikipedia, Self-avoiding walk

Crossrefs

Main diagonal of A347811.

Cf. A034841.

Programs

Maple

s:= proc(n) option remember;
     `if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
    end:
b:= proc(l) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
      add(i^2, i=h) b([n$n]):
seq(a(n), n=0..5);

Mathematica

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