|
| |
|
|
A091977
|
|
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.
|
|
0
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
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. - DELEHAM Philippe, Feb 06 2012
|
|
|
REFERENCES
| A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176).
|
|
|
FORMULA
| G.f.=G=G(t, z) satisfies tz(1-z)G^2-(1+tz-2z)G+1-z=0.
|
|
|
EXAMPLE
| 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...- DELEHAM Philippe, Feb 06 2012
|
|
|
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.
Sequence in context: A152195 A133156 A127529 * A112829 A121466 A065290
Adjacent sequences: A091974 A091975 A091976 * A091978 A091979 A091980
|
|
|
KEYWORD
| nonn,tabf,changed
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 15 2004
|
| |
|
|
