A166302 Sum of pyramid weights of all Dyck paths of semilength n that have no ascents and no descents of length 1.

0, 0, 2, 3, 8, 19, 44, 106, 257, 628, 1549, 3844, 9588, 24020, 60391, 152298, 385085, 975904, 2478129, 6303861, 16060946, 40977605, 104682165, 267730426, 685451776, 1756593392, 4505537267, 11565724164, 29711413595, 76379060176, 196473781247

Offset: 0

Author

Emeric Deutsch, Nov 07 2009

Keywords

• nonn

Comments

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.

Examples

			a(5)=19 because the pyramid weights of (UUDD)(UUUDDD), (UUUDDD)(UUDD), U(UUDD)(UUDD)D, and (UUUUUDDDDD) are 5, 5, 4, and 5, respectively (the maximal pyramids are shown between parentheses).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

Crossrefs

Cf. A166301, A091866.

Programs

Maple

G := (1/2)*z*(2-z)*(1+z-z^2-sqrt((1+z+z^2)*(1-3*z+z^2)))/((1-z)*sqrt((1+z+z^2)*(1-3*z+z^2))): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);

Mathematica

CoefficientList[Series[1/2*x*(2-x)*(1+x-x^2-Sqrt[(1+x+x^2)*(1-3*x+x^2)]) /((1-x)*Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

PARI

z='z+O('z^50); concat([0,0], Vec(z*(2-z)*(1+z-z^2-sqrt((1+z+z^2)*(1-3*z+z^2)))/(2*(1-z)*sqrt((1+z+z^2)*(1-3*z+z^2))))) \\ G. C. Greubel, Mar 22 2017

Formula

a(n) = Sum_{k=0..n} k*A166301(n,k).

G.f.: z*(2-z)*[1+z-z^2-sqrt((1+z+z^2)*(1-3*z+z^2))]/[2*(1-z)*sqrt((1+z+z^2)*(1-3*z+z^2))].

a(n) ~ (3+sqrt(5))^(n+1/2) / (5^(1/4) * sqrt(Pi*n) * 2^(n+3/2)). - Vaclav Kotesovec, Mar 20 2014

D-finite with recurrence 2*(n-1)*(2494*n-8185)*a(n) +23*(-770*n^2+3867*n-3959)*a(n-1) +(13226*n^2-83741*n+101091)*a(n-2) +(-7734*n^2+51213*n-51521)*a(n-3) +(17710*n^2-114385*n+144471)*a(n-4) +(-13226*n^2+104701*n-162397)*a(n-5) +(2746*n-6149)*(n-7)*a(n-6)=0. - R. J. Mathar, Jul 24 2022