|
| |
|
|
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;
text;
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. - Philippe Deléham, Feb 06 2012
|
|
|
LINKS
|
|
|
|
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
|
|
|
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).
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
