

A114597


Triangle read by rows: T(n,k) is the number of hillfree Dyck paths of semilength n having pyramid weight k.


0



1, 1, 1, 1, 3, 2, 1, 5, 9, 3, 1, 7, 21, 23, 5, 1, 9, 38, 74, 56, 8, 1, 11, 60, 170, 237, 130, 13, 1, 13, 87, 325, 674, 706, 293, 21, 1, 15, 119, 553, 1535, 2442, 1994, 645, 34, 1, 17, 156, 868, 3030, 6542, 8259, 5401, 1395, 55, 1, 19, 198, 1284, 5411, 14840, 25738, 26441
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,5


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. Row sums are the Fine numbers (A000957). T(n,n)=fibonacci(n1) (A000045).


LINKS

Table of n, a(n) for n=2..64.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155176.


FORMULA

G.f.= G1, where G=G(t, z) satisfies z(1+tt^2*zt^3*z^2)G^2(1+z2t^2*z^2)G+1tz=0.


EXAMPLE

T(4,3)=3 because we have U(UD)(UUDD)D, U(UUDD)(UD)D and U(UD)(UD)(UD)D, where U=(1,1),D=(1,1) (the maximal pyramids are shown between parentheses).
Triangle begins:
1;
1,1;
1,3,2;
1,5,9,3;
1,7,21,23,5;
1,9,38,74,56,8;


MAPLE

G:=(1+z2*t^2*z^2sqrt((1z)*(1z4*t*z+4*t^2*z^2)))/2/z/(1+tt^2*zt^3*z^2)1: Gser:=simplify(series(G, z=0, 15)): for n from 2 to 13 do P[n]:=expand(coeff(Gser, z^n)) od: for n from 2 to 13 do seq(coeff(P[n], t^j), j=2..n) od; # yields sequence in triangular form


CROSSREFS

Cf. A000957, A091866, A000045.
Sequence in context: A077951 A077976 A021912 * A199479 A050165 A330784
Adjacent sequences: A114594 A114595 A114596 * A114598 A114599 A114600


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Dec 12 2005


EXTENSIONS

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013


STATUS

approved



