|
%I #12 Dec 03 2014 04:00:54
%S 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,
%T 13,1,13,87,325,674,706,293,21,1,15,119,553,1535,2442,1994,645,34,1,
%U 17,156,868,3030,6542,8259,5401,1395,55,1,19,198,1284,5411,14840,25738,26441
%N Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n having pyramid weight k.
%C 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(n-1) (A000045).
%H A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.
%F G.f.= G-1, where G=G(t, z) satisfies z(1+t-t^2*z-t^3*z^2)G^2-(1+z-2t^2*z^2)G+1-tz=0.
%e 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).
%e Triangle begins:
%e 1;
%e 1,1;
%e 1,3,2;
%e 1,5,9,3;
%e 1,7,21,23,5;
%e 1,9,38,74,56,8;
%p G:=(1+z-2*t^2*z^2-sqrt((1-z)*(1-z-4*t*z+4*t^2*z^2)))/2/z/(1+t-t^2*z-t^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
%Y Cf. A000957, A091866, A000045.
%K nonn,tabl
%O 2,5
%A _Emeric Deutsch_, Dec 12 2005
%E Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013
|
