login
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).
2
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 04 2011
STATUS
approved