A306814 Number T(n,k) of n-step paths from (0,0) to (0,k) that stay in the first quadrant (but may touch the axes) consisting of steps (-1,0), (0,1), (0,-1) and (1,-1); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 1, 7, 5, 6, 4, 0, 1, 10, 23, 9, 10, 5, 0, 1, 38, 35, 51, 14, 15, 6, 0, 1, 89, 131, 84, 94, 20, 21, 7, 0, 1, 229, 355, 309, 168, 155, 27, 28, 8, 0, 1, 752, 874, 947, 608, 300, 237, 35, 36, 9, 0, 1, 1873, 3081, 2292, 2075, 1070, 495, 343, 44, 45, 10, 0, 1

Offset: 0

Author

Alois P. Heinz, Mar 11 2019

Keywords

• nonn
• tabl
• walk

Examples

			T(4,2) = 3:
  [(0,0), (0,1), (0,0), (0,1), (0,2)],
  [(0,0), (0,1), (0,2), (0,1), (0,2)],
  [(0,0), (0,1), (0,2), (0,3), (0,2)].
Triangle T(n,k) begins:
    1;
    0,   1;
    1,   0,   1;
    1,   2,   0,   1;
    2,   3,   3,   0,   1;
    7,   5,   6,   4,   0,   1;
   10,  23,   9,  10,   5,   0,  1;
   38,  35,  51,  14,  15,   6,  0,  1;
   89, 131,  84,  94,  20,  21,  7,  0, 1;
  229, 355, 309, 168, 155,  27, 28,  8, 0, 1;
  752, 874, 947, 608, 300, 237, 35, 36, 9, 0, 1;
  ...
		

Links

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

Crossrefs

Column k=0 gives A151346.

Row sums give A151404.

T(2n,n) gives A306813.

T(n+1,n-1) gives A001477.

T(n+2,n-1) gives A000217.

T(n+3,n-1) gives A000096.

Cf. A199915.

Programs

Maple

b:= proc(n, x, y) option remember; `if`(min(n, x, y, n-x-y)<0, 0,
      `if`(n=0, 1, add(b(n-1, x-d[1], y-d[2]),
       d=[[-1, 0], [0, 1], [0, -1], [1, -1]])))
    end:
T:= (n, k)-> b(n, 0, k):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[n_, x_, y_] := b[n, x, y] = If[Min[n, x, y, n - x - y] < 0, 0, If[n == 0, 1, Sum[b[n - 1, x - d[[1]], y - d[[2]]], {d, {{-1, 0}, {0, 1}, {0, -1}, {1, -1}}}]]];
T[n_, k_] := b[n, 0, k];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 14 2020, after Maple *)