0,3

A pyramid in a Dyck word (path) is a factor of the form u^h d^h, h being the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d.

The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids. An exterior pair in a Dyck path is a pair consisting of a u and its matching d (when viewed as parentheses) which do not belong in any pyramid. Clearly, for a given Dyck path, the sum of its pyramid weight and the number of its exterior pairs is equal to the semilength of the path.

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176).

G.f.=G=G(t, z) satisfies tz(1-z)G^2-(1+tz-2z)G+1-z=0.

T(4,1)=5 because the Dyck paths of semilength 4 having 1 exterior pair are: ud(u)udud(d), (u)udud(d)ud, (u)ududud(d), (u)uduudd(d) and (u)uuuddud(d) [the u and d that form the unique exterior pair are shown between parentheses].

Triangle begins:

[1],

[1],

[2],

[4, 1],

[8, 5, 1],

[16, 18, 7, 1],

[32, 56, 34, 9, 1],

[64, 160, 138, 55, 11, 1],

[128, 432, 500, 275, 81, 13, 1]

T(n, k)=A091866(n, n-k), T(n, 0)=2^(n-1) (n>0), T(n, 1)=A001793(n-2), row sums give the Catalan numbers (A000108).

Cf. A091866, A001793, A000108.

Sequence in context: A152195 A133156 A127529 this_sequence A112829 A121466 A065290

Adjacent sequences: A091974 A091975 A091976 this_sequence A091978 A091979 A091980

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 15 2004