|
%I #8 Dec 02 2014 16:26:50
%S 1,1,1,1,1,3,1,6,2,1,12,8,1,24,22,4,1,48,58,20,1,96,149,69,8,1,192,
%T 373,221,48,1,384,914,675,198,16,1,768,2200,1977,740,112,1,1536,5216,
%U 5597,2593,536,32,1,3072,12208,15407,8611,2280,256,1,6144,28256,41418,27389
%N Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having trapezoid weight k.
%C A Motzkin path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(1,0) and never going below the x-axis. Motzkin paths are counted by the Motzkin numbers (A001006).
%C A trapezoid in a Motzkin path is a factor of the form U^i H^j D^i (i>=1, j>=0), i being the height of the trapezoid. A trapezoid in a Motzkin path w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The trapezoid weight of a Motzkin path is the sum of the heights of its maximal trapezoids. For example, in the Motzkin path w=UH(UHD)D(UUDD) we have two maximal trapezoids (shown between parentheses) of heights 1 and 2, respectively. The trapezoid weight of w is 1+2=3.
%C This concept is analogous to the concept of pyramid weight in a Dyck path (see the Denise-Simion paper).
%C Row sums yield the Motzkin numbers (A001006).
%C Row n has 1+floor(n/2) terms.
%C T(2n+1,n)=(n+2)*2^(n-1) (A001792).
%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=G(t, z) satisfies G=1+zG+z^2[G-(1-t)/((1-z)(1-tz^2))]G.
%e Triangle begins:
%e 1;
%e 1;
%e 1,1;
%e 1,3;
%e 1,6,2;
%e 1,12,8;
%e 1,24,22,4;
%e T(4,0)=1,T(4,1)=6, T(4,2)=2 because the nine Motzkin paths of length 4, namely HHHH, HH(UD),H(UD)H,H(UHD),(UD)HH,(UD)(UD),(UHD)H,(UHHD),(UUDD), have trapezoid weights 0,1,1,1,1,2,1,1,2, respectively; the maximal trapezoids are shown between parentheses.
%Y Cf. A001006, A001792, A104574.
%K nonn,tabf
%O 0,6
%A _Emeric Deutsch_, Mar 16 2005
|
