A282869 Triangle read by rows: T(n,k) is the number of dispersed Dyck prefixes (i.e., left factors of Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 7, 5, 2, 1, 1, 12, 10, 6, 2, 1, 1, 20, 21, 12, 7, 2, 1, 1, 33, 41, 28, 14, 8, 2, 1, 1, 54, 81, 56, 36, 16, 9, 2, 1, 1, 88, 155, 120, 72, 45, 18, 10, 2, 1, 1, 143, 297, 239, 165, 90, 55, 20, 11, 2, 1, 1, 232, 560, 492, 330, 220, 110, 66, 22, 12, 2, 1, 1, 376, 1054, 974, 715, 440, 286, 132, 78, 24, 13, 2, 1

Offset: 0

Author

Steven Finch, Feb 23 2017

Keywords

• nonn
• tabl

Comments

Row n has n+1 entries.

Examples

			Triangle starts:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  2,  1;
  1,  7,  5,  2, 1;
  1, 12, 10,  6, 2, 1;
  1, 20, 21, 12, 7, 2, 1;
  ...
T(4,3) = 2 because we have UUUD and HUUU, where U=(1,1), D=(1,-1), H=(1,0).
T(4,2) = 5 because we have UUDD, UUDU, UDUU, HUUD and HHUU.
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.

Crossrefs

Row sums give A000079.

T(2n,n) gives A283799.

Cf. A000071, A191314.

Programs

Maple

b:= proc(x, y, m) option remember;
      `if`(x=0, z^m, `if`(y>0, b(x-1, y-1, m), 0)+
      `if`(y=0, b(x-1, y, m), 0)+b(x-1, y+1, max(m, y+1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..16);  # Alois P. Heinz, Mar 13 2017

Mathematica

b[x_, y_, m_] := b[x, y, m] = If[x == 0, z^m, If[y > 0, b[x - 1, y - 1, m], 0] + If[y == 0, b[x - 1, y, m], 0] + b[x - 1, y + 1, Max[m, y + 1]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][ b[n, 0, 0]];
Table[T[n], {n, 0, 16}] // Flatten (* Jean-François Alcover, May 12 2017, after Alois P. Heinz *)

Formula

T(n,1) = A000071(n+1), (Fibonacci numbers minus 1).