A191305 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths (i.e., Motzkin paths with no (1,0) steps at positive heights) of length n having k hills (i.e., peaks at height 1).

1, 1, 1, 1, 1, 2, 2, 3, 1, 3, 4, 3, 6, 7, 6, 1, 9, 12, 10, 4, 18, 23, 18, 10, 1, 28, 40, 33, 20, 5, 57, 76, 64, 39, 15, 1, 91, 134, 120, 76, 35, 6, 187, 257, 231, 152, 75, 21, 1, 304, 460, 433, 300, 156, 56, 7, 629, 888, 834, 595, 325, 132, 28, 1, 1037, 1606, 1572, 1164, 670, 294, 84, 8, 2157, 3115, 3035, 2292, 1375, 642, 217, 36, 1

Offset: 0

Author

Emeric Deutsch, May 30 2011

Keywords

• nonn
• tabf

Comments

Row n has 1 + floor(n/2) entries.

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

Sum_{k>=0}k*T(n,k) = A045621(n-2).

Examples

			T(5,2)=3 because we have HUDUD, UDHUD, and UDUDH, where U=(1,1), D=(1,-1), H=(1,0).
Triangle starts:
  1;
  1;
  1,  1;
  1,  2;
  2,  3,  1;
  3,  4,  3;
  6,  7,  6,  1;
  9, 12, 10,  4;
		

Crossrefs

Cf. A001405, A045621.

Programs

Maple

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

Formula

G.f.: G=G(t,z) satisfies G = 1+z*G + z^2*G(C-1+t), where C=1+z^2*C^2 (and G=2/(1-2*z+2*z^2-2*t*z^2+sqrt(1-4*z^2)), see Maple program).