A171852 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).

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, 173, 51, 6, 1, 384, 421, 147, 24, 1, 1, 768, 1010, 415, 82, 7, 1, 1536, 2392, 1147, 264, 32, 1, 1, 3072, 5600, 3107, 825, 122, 8, 1, 6144, 12976, 8265, 2513, 431, 41, 1, 1, 12288

Offset

0,7

Comments

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).

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.

The sum of the entries in row n is A004148(n) (the secondary structure numbers).

Sum(k*T(n,k), k>=0) = A171853(n).

Links

Table of n, a(n) for n=0..66.

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

Formula

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)].

Example

T(4,1)=3 because each of the paths HUHD, UHHD and UHDH has trapezoid weight 1.
Triangle starts:
1;
1;
1;
1,1;
1,3;
1,6,1;
1,12,4;
1,24,11,1

Maple

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

Crossrefs

Cf. A004148, A171853.

Sequence in context: A089732 A158905 A098076 * A010287 A130270 A225599

Adjacent sequences: A171849 A171850 A171851 * A171853 A171854 A171855

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 08 2010

Status

approved