A347811 Number A(n,k) of k-dimensional lattice walks from {n}^k to {0}^k using steps that decrease the Euclidean distance to the origin and that change each coordinate by at most 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 19, 25, 1, 1, 1, 323, 211075, 241, 1, 1, 1, 38716, 1322634996717, 2062017739, 2545, 1, 1, 1, 32253681, 16042961630858858915656, 29261778984922904560001, 32191353922714, 28203, 1, 1

Offset

0,8

Comments

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

Links

Alois P. Heinz, Antidiagonals n = 0..11, flattened

Alois P. Heinz, Animation of A(2,2) = 25 walks

Wikipedia, Counting lattice paths

Wikipedia, Self-avoiding walk

Example

Square array A(n,k) begins:
  1, 1,     1,              1,                       1,     1, ...
  1, 1,     3,             19,                     323, 38716, ...
  1, 1,    25,         211075,           1322634996717, ...
  1, 1,   241,     2062017739, 29261778984922904560001, ...
  1, 1,  2545, 32191353922714, ...
  1, 1, 28203, ...
  ...

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, k)-> b([n$k]):
seq(seq(A(n, d-n), n=0..d), d=0..8);

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_, k_] := b[Table[n, {k}]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 8}] // Flatten (* Jean-François Alcover, Nov 03 2021, after Alois P. Heinz *)

Crossrefs

Columns k=0+1, 2-3 give: A000012, A346539, A347813.

Rows n=0-2 give: A000012, A346840, A347812.

Main diagonal gives A347810.

Cf. A089759, A187783, A335570.

Sequence in context: A070989 A274741 A135021 * A320412 A286591 A297557

Adjacent sequences: A347808 A347809 A347810 * A347812 A347813 A347814

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Sep 14 2021

Status

approved