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

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

Links

Table of n, a(n) for n=0..80.

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

Example

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;

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

Crossrefs

Cf. A001405, A045621.

Sequence in context: A205456 A080045 A191384 * A227287 A289236 A280172

Adjacent sequences: A191302 A191303 A191304 * A191306 A191307 A191308

Keyword

nonn,tabf

Author

Emeric Deutsch, May 30 2011

Status

approved