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

1, 1, 1, 3, 3, 3, 7, 5, 5, 7, 19, 24, 13, 24, 19, 51, 81, 25, 25, 81, 51, 141, 298, 173, 63, 173, 298, 141, 393, 1070, 739, 129, 129, 739, 1070, 393, 1107, 3868, 3423, 1210, 321, 1210, 3423, 3868, 1107, 3139, 13960, 15363, 6273, 681, 681, 6273, 15363, 13960, 3139

Offset

0,4

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

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

Wikipedia, Counting lattice paths

Wikipedia, Self-avoiding walk

Formula

A(n,k) = A(k,n).

Example

Square array A(n,k) begins:
    1,    1,     3,     7,    19,    51,   141,   393, ...
    1,    3,     5,    24,    81,   298,  1070,  3868, ...
    3,    5,    13,    25,   173,   739,  3423, 15363, ...
    7,   24,    25,    63,   129,  1210,  6273, 34318, ...
   19,   81,   173,   129,   321,   681,  8371, 51727, ...
   51,  298,   739,  1210,   681,  1683,  3653, 57644, ...
  141, 1070,  3423,  6273,  8371,  3653,  8989, 19825, ...
  393, 3868, 15363, 34318, 51727, 57644, 19825, 48639, ...
  ...

Maple

s:= proc(n) option remember;
     `if`(n=0, [[]], map(x-> seq([x[], i], i=-1..1), s(n-1)))
    end:
b:= proc(l, v) option remember; (n-> `if`(l=[0$n], 1, add((h-> `if`(
      add(i^2, i=h)<add(i^2, i=l) and add(i^2, i=v-h)>add(i^2, i=v-l)
      , b(h, v), 0))(l+x), x=s(n))))(nops(l))
    end:
A:= (n, k)-> b(sort([n, k])$2):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

s[n_] := s[n] = If[n == 0, {{}}, Sequence @@
     Table[Append[#, i], {i, -1, 1}]& /@ s[n-1]];
b[l_, v_] := b[l, v] = With[{n = Length[l]},
     If[l == Table[0, {n}], 1, Sum[With[{h = l+x},
     If[h.h<l.l && (v-h).(v-h)>(v-l).(v-l), b[h, v], 0]], {x, s[n]}]]];
A[n_, k_] := b[Sort[{n, k}], Sort[{n, k}]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Nov 04 2021, after Alois P. Heinz *)

Crossrefs

Columns (or rows) k=0-1 give: A002426, A347947.

Main diagonal gives A001850.

A(2n,n) gives A346541.

A(n-1,n) gives A002002 for n >= 1.

Sequence in context: A294505 A242016 A084038 * A326930 A095108 A132197

Adjacent sequences: A346537 A346538 A346539 * A346541 A346542 A346543

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Sep 16 2021

Status

approved