A328347 Number T(n,k) of n-step walks on cubic lattice starting at (0,0,0), ending at (0,k,n-k) and using steps (0,0,1), (0,1,0), (1,0,0), (-1,1,1), (1,-1,1), and (1,1,-1); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 3, 4, 3, 7, 15, 15, 7, 19, 52, 72, 52, 19, 51, 175, 300, 300, 175, 51, 141, 576, 1185, 1480, 1185, 576, 141, 393, 1869, 4473, 6685, 6685, 4473, 1869, 393, 1107, 6000, 16380, 28392, 33880, 28392, 16380, 6000, 1107, 3139, 19107, 58572, 115332, 159264, 159264, 115332, 58572, 19107, 3139

Offset: 0

Author

Alois P. Heinz, Oct 13 2019

Keywords

• nonn
• tabl
• walk

Comments

These walks are not restricted to the first (nonnegative) octant.

Examples

			Triangle T(n,k) begins:
     1;
     1,    1;
     3,    4,     3;
     7,   15,    15,     7;
    19,   52,    72,    52,    19;
    51,  175,   300,   300,   175,    51;
   141,  576,  1185,  1480,  1185,   576,   141;
   393, 1869,  4473,  6685,  6685,  4473,  1869,  393;
  1107, 6000, 16380, 28392, 33880, 28392, 16380, 6000, 1107;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Wikipedia, Lattice path
• Wikipedia, Self-avoiding walk

Crossrefs

Columns k=0-1 give: A002426, A132894 = n*A005773(n).

Row sums give A084609.

T(2n,n) gives A328426.

Cf. A007318, A328300, A328345.

Programs

Maple

b:= proc(l) option remember; `if`(l[-1]=0, 1, (r-> add(add(
      add(`if`(i+j+k=1, (h-> `if`(add(t, t=h)<0, 0, b(h)))(
      sort(l-[i, j, k])), 0), k=r), j=r), i=r))([$-1..1]))
    end:
T:= (n, k)-> b(sort([0, k, n-k])):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[l_List] := b[l] = If[l[[-1]] == 0, 1, Sum[If[i + j + k == 1, Function[h, If[Total[h] < 0, 0, b[h]]][Sort[l - {i, j, k}]], 0], {i, {-1, 0, 1}}, {j, {-1, 0, 1}}, {k, {-1, 0, 1}}]];
T[n_, k_] := b[Sort[{0, k, n - k}]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

Formula

T(n,k) = T(n,n-k).