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

Author

Alois P. Heinz, Sep 16 2021

Keywords

• nonn
• tabl
• walk

Comments

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

Examples

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

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

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.

Programs

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

Formula

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