A347813 -id:A347813 - cp's OEIS frontend

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

Alois P. Heinz, Sep 14 2021

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

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

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

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.

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

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 *)

A348201 Number of walks on cubic lattice from (n,n,n) to (0,0,0) using steps that decrease the Euclidean distance to the origin and that change each coordinate by 1 or by -1.

Original entry on oeis.org

1, 1, 25, 211, 4057, 79945, 1559719, 34166335, 784027759, 18367309153, 447879467629, 11160419719795, 283032843838285, 7307188685246689, 191139484940529781, 5056715112537049897, 135152031778121985907, 3642958379395296513337, 98930628058690700138443

Offset: 0

Alois P. Heinz, Oct 06 2021

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

All terms are odd.

			a(2) = 25:
  ((2,2,2), (1,1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,0,2), (-1,-1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,0,2), (-1,1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,0,2), (1,-1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,0,2), (1,1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,2,2), (-1,1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (0,2,2), (1,1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (2,0,2), (1,-1,1), (0,0,0)),
  ((2,2,2), (1,1,3), (2,0,2), (1,1,1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,0), (-1,1,-1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,0), (-1,1,1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,0), (1,1,-1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,0), (1,1,1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,2), (-1,1,1), (0,0,0)),
  ((2,2,2), (1,3,1), (0,2,2), (1,1,1), (0,0,0)),
  ((2,2,2), (1,3,1), (2,2,0), (1,1,-1), (0,0,0)),
  ((2,2,2), (1,3,1), (2,2,0), (1,1,1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,0), (1,-1,-1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,0), (1,-1,1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,0), (1,1,-1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,0), (1,1,1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,2), (1,-1,1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,0,2), (1,1,1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,2,0), (1,1,-1), (0,0,0)),
  ((2,2,2), (3,1,1), (2,2,0), (1,1,1), (0,0,0)).

Alois P. Heinz, Table of n, a(n) for n = 0..681
Wikipedia, Counting lattice paths
Wikipedia, Self-avoiding walk

Cf. A347813.

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

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

a(n) ~ c * d^n / n, where d = (3*(292 + 4*sqrt(5))^(1/3))/2 + 66/(292 + 4*sqrt(5))^(1/3) + 10 = 29.900786688498085577218938127572448... and c = 0.00221301854906444252905280527969234142... - Vaclav Kotesovec, Oct 24 2021

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica