A191390 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths of length n with k horizontal segments.

1, 0, 1, 1, 1, 0, 3, 2, 3, 1, 0, 8, 2, 5, 8, 7, 0, 22, 12, 1, 14, 22, 31, 3, 0, 64, 50, 12, 42, 64, 117, 28, 1, 0, 196, 184, 78, 4, 132, 196, 416, 162, 18, 0, 625, 648, 390, 52, 1, 429, 625, 1452, 762, 159, 5, 0, 2055, 2256, 1707, 392, 25, 1430, 2055, 5062, 3225, 1012, 85, 1, 0, 6917, 7868, 6954, 2280, 285, 6

Offset: 0

Author

Emeric Deutsch, Jun 03 2011

Keywords

• nonn
• tabf

Comments

A dispersed Dyck paths of length n is a Motzkin paths of length n with no (1,0)-steps at positive heights. A horizontal segment is a maximal sequence of consecutive (1,0)-steps.

Row n has 1 + ceiling(n/3) entries.

Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).

T(2n,0) = A000108(n) (the Catalan numbers); T(2n+1,0) = 0.

T(2n-1,1) = T(2n,1) = A014138(n) (partial sums of Catalan numbers).

Sum_{k>=0} k*T(n,k) = A191391(n).

Examples

			T(5,2)=2 because we have (HH)UD(H) and (H)UD(HH), where U=(1,1), D=(1,-1), H=(1,0) (the horizontal segments are shown between parentheses).
Triangle starts:
  1;
  0,  1;
  1,  1;
  0,  3;
  2,  3,  1;
  0,  8,  2;
  5,  8,  7;
  0, 22, 12,  1;
		

Crossrefs

Cf. A000108, A001405, A014138, A191391.

Programs

Maple

G := (2*(1-z+t*z))/(1-z-t*z+(1-z+t*z)*sqrt(1-4*z^2)): Gser := simplify(series(G, z = 0, 20)): for n from 0 to 17 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 17 do seq(coeff(P[n], t, k), k = 0 .. ceil((1/3)*n)) end do; # yields sequence in triangular form

Formula

G.f.: G(t,z) = (2*(1-z+t*z))/(1-z-t*z+(1-z+t*z)*sqrt(1-4*z^2)).