|
%I #6 Dec 02 2014 16:29:41
%S 1,1,1,1,1,1,3,1,6,1,1,12,4,1,24,11,1,1,48,28,5,1,96,70,17,1,1,192,
%T 173,51,6,1,384,421,147,24,1,1,768,1010,415,82,7,1,1536,2392,1147,264,
%U 32,1,1,3072,5600,3107,825,122,8,1,6144,12976,8265,2513,431,41,1,1,12288
%N Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having trapezoid weight k (n>=0, k>=0).
%C A trapezoid in a peakless Motzkin path is a factor of the form U^i H^j D^i (i, j>=1), i being the height of the trapezoid and U=(1,1), H=(1,0), D=(1,-1). A trapezoid in a peakless 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 peakless Motzkin path is the sum of the heights of its maximal trapezoids. For example, in the peakless Motzkin path w=UH(UHD)D(UUHHDD) we have two maximal trapezoids (shown between parentheses) of heights 1 and 2, respectively. The trapezoid weight of w is 1+2=3. This concept is analogous to the concept of pyramid weight in a Dyck path (see the Denise-Simion paper).
%C The number of terms in rows 0,1,2,3,4,5,6,7,... is 1,1,1,2,2,3,3,4,4,5,5,..., respectively.
%C The sum of the entries in row n is A004148(n) (the secondary structure numbers).
%C Sum(k*T(n,k), k>=0) = A171853(n).
%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 The g.f. G=G(t,z) satisfies G = 1 + zG + z^2*G*(G - 1 + z*(t - 1)/[(1 - z)(1 - t*z^2)].
%e T(4,1)=3 because each of the paths HUHD, UHHD and UHDH has trapezoid weight 1.
%e Triangle starts:
%e 1;
%e 1;
%e 1;
%e 1,1;
%e 1,3;
%e 1,6,1;
%e 1,12,4;
%e 1,24,11,1
%p eq := G = 1+z*G+z^2*G*(G-1+z*(t-1)/((1-z)*(1-t*z^2))): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 20)): for n from 0 to 16 do P[n] := sort(coeff(Gser, z, n)) end do: 1; for n to 16 do seq(coeff(P[n], t, k), k = 0 .. floor(((n^2-1)*1/2)/n)) end do; # yields sequence in triangular form
%Y Cf. A004148, A171853.
%K nonn,tabf
%O 0,7
%A _Emeric Deutsch_, Feb 08 2010
|
