

A171853


Sum of the trapezoid weights of all peakless Motzkin paths of length n (n>=0).


1



0, 0, 0, 1, 3, 8, 20, 49, 119, 291, 715, 1768, 4396, 10983, 27551, 69351, 175081, 443119, 1123963, 2856383, 7271377, 18538391, 47327615, 120972510, 309555666, 792917565, 2032905981, 5216436109, 13395813003, 34425270629, 88527064337
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


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


LINKS

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


FORMULA

a(n) = Sum(k*A171852(n,k), k>=0).
G.f.=z^3*g/[(1 + z)(1  z + z^2  2z^2*g)(1  z)^2], where g=g(z) satisfies g=1+zg+z^2*g(g1).
Conjecture: (n+1)*a(n) +(3*n5)*a(n1) +(n+7)*a(n2) 7*a(n3) 5*a(n4) 7*a(n5) +n*a(n6) +(3*n+16)*a(n7) +(n6)*a(n8)=0.  R. J. Mathar, Dec 07 2017


EXAMPLE

a(4)=3 because the 4 (=A004148(4)) peakless Motzkin paths of length 4, namely HHHH, HUHD, UHHD and UHDH have trapezoid weights 0, 1, 1 and 1, respectively.


MAPLE

eqg := g = 1+z*g+z^2*g*(g1): g := RootOf(eqg, g): G := z^3*g/((1+z)*(1z)^2*(1z+z^22*z^2*g)): Gser := series(G, z = 0, 38): seq(coeff(Gser, z, n), n = 0 .. 35);


CROSSREFS

Cf. A004148, A171852.
Sequence in context: A054192 A124523 A054185 * A330458 A093963 A261233
Adjacent sequences: A171850 A171851 A171852 * A171854 A171855 A171856


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Feb 08 2010


STATUS

approved



