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

Comments

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

Links

Alois P. Heinz, Rows n = 0..200, flattened

Wikipedia, Lattice path

Wikipedia, Self-avoiding walk

Formula

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

Example

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

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

Crossrefs

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

Row sums give A084609.

T(2n,n) gives A328426.

Cf. A007318, A328300, A328345.

Sequence in context: A163108 A350771 A077005 * A265723 A134065 A015887

Adjacent sequences: A328344 A328345 A328346 * A328348 A328349 A328350

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Oct 13 2019

Status

approved