A346840 Number of n-dimensional lattice walks from {1}^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, 3, 19, 323, 38716, 32253681, 78267222216, 762698791293515, 37603168183752885658, 9243338412512497704718998, 11335247475355582487279558180986, 68305298969167998414438069494886302081, 1920885596256995709122789811280666218400361901

Offset

0,3

Comments

Lattice points may have negative coordinates, and different walks may differ in length. All walks are self-avoiding.

Links

Table of n, a(n) for n=0..13.

Wikipedia, Counting lattice paths

Wikipedia, Self-avoiding walk

Example

a(3) = 19:
  ((1,1,1), (0,0,0)),
  ((1,1,1), (0,0,1), (0,0,0)),
  ((1,1,1), (0,1,0), (0,0,0)),
  ((1,1,1), (0,1,1), (0,0,0)),
  ((1,1,1), (1,0,0), (0,0,0)),
  ((1,1,1), (1,0,1), (0,0,0)),
  ((1,1,1), (1,1,0), (0,0,0)),
  ((1,1,1), (0,1,1), (-1,0,0), (0,0,0)),
  ((1,1,1), (0,1,1), (0,0,1), (0,0,0)),
  ((1,1,1), (0,1,1), (0,1,0), (0,0,0)),
  ((1,1,1), (0,1,1), (1,0,0), (0,0,0)),
  ((1,1,1), (1,0,1), (0,-1,0), (0,0,0)),
  ((1,1,1), (1,0,1), (0,0,1), (0,0,0)),
  ((1,1,1), (1,0,1), (0,1,0), (0,0,0)),
  ((1,1,1), (1,0,1), (1,0,0), (0,0,0)),
  ((1,1,1), (1,1,0), (0,0,-1), (0,0,0)),
  ((1,1,1), (1,1,0), (0,0,1), (0,0,0)),
  ((1,1,1), (1,1,0), (0,1,0), (0,0,0)),
  ((1,1,1), (1,1,0), (1,0,0), (0,0,0)).

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([1$n]):
seq(a(n), n=0..10);

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

Crossrefs

Row n=1 of A347811.

Sequence in context: A136171 A102586 A326902 * A132876 A357956 A229832

Adjacent sequences: A346837 A346838 A346839 * A346841 A346842 A346843

Keyword

nonn,walk

Author

Alois P. Heinz, Sep 14 2021

Status

approved