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

Comments

Row n has n+1 entries.

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.

Formula

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

Example

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.

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

Crossrefs

Row sums give A000079.

T(2n,n) gives A283799.

Cf. A000071, A191314.

Sequence in context: A098063 A209438 A106396 * A140998 A048004 A114394

Adjacent sequences: A282866 A282867 A282868 * A282870 A282871 A282872

Keyword

nonn,tabl

Author

Steven Finch, Feb 23 2017

Status

approved