A216318 Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.

0, 1, 2, 8, 31, 119, 456, 1749, 6721, 25883, 99892, 386308, 1496782, 5809478, 22584160, 87922215, 342741285, 1337698515, 5226732060, 20442936360, 80031775890, 313585934610, 1229695855440, 4825705232010, 18950613058026, 74467158658974, 292797216620776, 1151895428382104

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Formula

a(0)=0, a(1)=1, a(n>=2) = A001700(n-1) - Sum_{k=0..n-3} A001700(k) + Sum_{k=0..n-2} A003516(k) - 1.

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

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

a(n) = C(2*n-2,n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 30 2020

Example

The 5 Dyck 3-paths after changing DU to UD become two copies of UUUDDD with one peak each and three copies of UUDUDD with two peaks each giving a(3)=8.

Mathematica

CoefficientList[Series[(16*x*(1+Sqrt[1-4*x]+(5+3*Sqrt[1-4*x]-2*x)*(-1+x) x))/((1+Sqrt[1-4*x])^5*Sqrt[1-4*x]), {x, 0, 27}], x]

Prog

(PARI) x='x+O('x^50); concat([0], Vec((16*x*(1+sqrt(1-4*x)-(5+3*sqrt(1-4*x)-2*x)*(1-x)*x)) / ((1+sqrt(1-4*x))^5*sqrt(1-4*x)))) \\ G. C. Greubel, Apr 01 2017
(Maxima)
a(n):=if n<2 then n else binomial(2*n-2, n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)); /* Vladimir Kruchinin, Oct 30 2020 */

Crossrefs

Cf. A001700, A003516, A005891.

Sequence in context: A062456 A289610 A077838 * A018916 A281831 A206229

Adjacent sequences: A216315 A216316 A216317 * A216319 A216320 A216321

Keyword

nonn

Author

David Scambler, Sep 03 2012

Status

approved