login
A216318
Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.
1
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
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
KEYWORD
nonn
AUTHOR
David Scambler, Sep 03 2012
STATUS
approved