A191394 Number of base pyramids in all dispersed Dyck paths of length n (i.e., in all Motzkin paths of length n with no (1,0)-steps at positive heights).

0, 0, 1, 2, 6, 12, 28, 56, 121, 242, 507, 1014, 2093, 4186, 8569, 17138, 34902, 69804, 141664, 283328, 573574, 1147148, 2318010, 4636020, 9354540, 18709080, 37708672, 75417344, 151868100, 303736200, 611180252, 1222360504, 2458123705, 4916247410, 9881255187

Offset

0,4

Comments

A base pyramid is a factor of the form U^j D^j (j>0), starting at the horizontal axis. Here U=(1,1) and D=(1,-1).

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

a(n) = Sum_{k=0..(1 + ceiling(n/2))} k*A191392(n, k), formula clarified by G. C. Greubel.

G.f.: 4*x^2/((1-x^2)*(1-2*x+sqrt(1-4*x^2))^2).

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

a(n) = ceiling(2*(2^n-1)/3) - Sum_{i=1..(n+1)/2} binomial(n-2*i+1, floor((n-2*i+1)/2)) = A000975(n) - A174783(n). - Vladimir Kruchinin, Mar 15 2016

D-finite with recurrence n*a(n) -2*n*a(n-1) +(-5*n+12)*a(n-2) +2*(5*n-12)*a(n-3) +4*(n-3)*a(n-4) +8*(-n+3)*a(n-5)=0. - R. J. Mathar, Jun 14 2016

Example

a(4) = 6 because in HHHH, HH(UD), H(UD)H, (UD)HH, (UD)(UD), and (UUDD) we have a total of 0+1+1+1+2+1 = 6 base pyramids (shown between parentheses).

Maple

G := 4*z^2/((1-z^2)*(1-2*z+sqrt(1-4*z^2))^2): Gser := series(G, z = 0, 38): seq(coeff(Gser, z, n), n = 0 .. 34);

Mathematica

CoefficientList[Series[(4x^2)/((1-x^2)(1-2x+Sqrt[1-4x^2])^2), {x, 0, 40}], x] (* Harvey P. Dale, Jun 19 2011 *)

Prog

(Maxima) a(n):=ceiling(2*(2^n-1)/3)-sum((binomial(n-2*i+1, floor((n-2*i+1)/2))), i, 1, (n+1)/2); /* Vladimir Kruchinin, Mar 15 2016 */
(PARI) x='x+O('x^50); concat([0, 0], Vec(4*x^2/((1-x^2)*(1-2*x+sqrt(1-4*x^2))^2))) \\ G. C. Greubel, Mar 26 2017

Crossrefs

Cf. A000975, A174783, A191392.

Sequence in context: A350271 A089820 A122746 * A237500 A330455 A183467

Adjacent sequences: A191391 A191392 A191393 * A191395 A191396 A191397

Keyword

nonn

Author

Emeric Deutsch, Jun 04 2011

Status

approved