A328300 Number T(n,k) of n-step walks on cubic lattice starting at (0,0,0), ending at (0,k,n-k), remaining in the first (nonnegative) octant 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, 1, 3, 1, 1, 7, 7, 1, 1, 15, 26, 15, 1, 1, 31, 82, 82, 31, 1, 1, 63, 237, 343, 237, 63, 1, 1, 127, 651, 1257, 1257, 651, 127, 1, 1, 255, 1730, 4256, 5594, 4256, 1730, 255, 1, 1, 511, 4494, 13669, 22411, 22411, 13669, 4494, 511, 1, 1, 1023, 11485, 42279, 83680, 103730, 83680, 42279, 11485, 1023, 1

Offset

0,5

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;
  1,   3,    1;
  1,   7,    7,    1;
  1,  15,   26,   15,    1;
  1,  31,   82,   82,   31,    1;
  1,  63,  237,  343,  237,   63,    1;
  1, 127,  651, 1257, 1257,  651,  127,   1;
  1, 255, 1730, 4256, 5594, 4256, 1730, 255, 1;
  ...

Maple

b:= proc(l) option remember; `if`(l[-1]=0, 1, (r-> add(
      add(add(`if`(i+j+k=1, (h-> `if`(h[1]<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, Function[r, Sum[Sum[Sum[If[i + j + k == 1, Function[h, If[h[[1]] < 0, 0, b[h]]][Sort[l - {i, j, k}]], 0], {k, r}], {j, r}], {i, r}]][{-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, May 10 2020, after Maple *)

Crossrefs

Columns k=0-1 give: A000012, A000225.

Row sums give A328296.

T(2n,n) gives A328269.

T(n,floor(n/2)) gives A328280.

Cf. A007318, A008288, A091533, A328297, A328347.

Sequence in context: A344527 A193871 A108470 * A157152 A136126 A046802

Adjacent sequences: A328297 A328298 A328299 * A328301 A328302 A328303

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Oct 11 2019

Status

approved