A091977 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.

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, 256, 1120, 1672, 1205, 481, 112, 15, 1, 512, 2816, 5264, 4797, 2471, 770, 148, 17, 1, 1024, 6912, 15808, 17738, 11403, 4536, 1156, 189, 19, 1, 2048, 16640

Offset: 0

Author

Emeric Deutsch, Mar 15 2004

Keywords

• nonn
• tabf

Comments

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.

Triangle, with zeros omitted, given by (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...) DELTA (0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 06 2012

Examples

			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]
Triangle (1,1,0,1,1,0,1,1,...) DELTA (0,0,1,0,0,1,0,0,1,...) begins :
1
1, 0
2, 0, 0
4, 1, 0, 0
8, 5, 1, 0, 0
16, 18, 7, 1, 0, 0
32, 56, 34, 9, 1, 0, 0
64, 160, 138, 55, 11, 1, 0, 0...- _Philippe Deléham_, Feb 06 2012
		

Links

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

Crossrefs

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.

Formula

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