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,3

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

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)<add(i^2, i=l), b(sort(h)), 0))(l+x), x=s(n))))(nops(l))
    end:
a:= n-> 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 *)

Crossrefs

Main diagonal of A347811.

Cf. A034841.

Sequence in context: A191559 A279039 A237522 * A116197 A023924 A022066

Adjacent sequences: A347807 A347808 A347809 * A347811 A347812 A347813

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 14 2021

Status

approved