login
A121532
Number of double rises at an even level in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.
2
0, 0, 1, 6, 24, 87, 290, 926, 2861, 8640, 25634, 75015, 217100, 622620, 1772097, 5011394, 14093980, 39448623, 109954398, 305344314, 845165725, 2332485420, 6420202246, 17629525871, 48304680504, 132092031672, 360557665825
OFFSET
1,4
LINKS
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
FORMULA
a(n) = Sum_{k>=0} k*A121531(n,k).
a(n) = A054444(n-2) - A121530(n).
G.f.: x^3*(1-3*x^2+2*x^3-x^4)/((1+x)*(1-3*x+x^2)^2*(1-x-x^2)). [Corrected by Georg Fischer, May 24 2019]
a(n) ~ (3-sqrt(5)) * (3+sqrt(5))^n * n / (5 * 2^(n+1)). - Vaclav Kotesovec, Mar 20 2014
Equivalently, a(n) ~ phi^(2*n-2) * n / 5, where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 06 2021
EXAMPLE
a(3)=1 because we have UDUDUD, UDUUDD, UUDDUD, UUDUDD and UU/UDDD, the double rises at an odd level being indicated by a / (U=(1,1), D=(1,-1)).
MAPLE
g:=z^3*(1-3*z^2+2*z^3-z^4)/(1+z)/(1-3*z+z^2)^2/(1-z-z^2): gser:=series(g, z=0, 35): seq(coeff(gser, z, n), n=1..32);
MATHEMATICA
Rest[CoefficientList[Series[x^3*(1-3*x^2+2*x^3-x^4)/(1+x)/(1-3*x+x^2)^2/(1-x-x^2), {x, 0, 30}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)
PROG
(PARI) my(x='x+O('x^30)); concat([0, 0], Vec(x^3*(1-3*x^2+2*x^3-x^4)/((1+x)*(1-3*x+x^2)^2*(1-x-x^2)))) \\ G. C. Greubel, May 24 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 30); [0, 0] cat Coefficients(R!( x^3*(1-3*x^2+2*x^3-x^4)/((1+x)*(1-3*x+x^2)^2*(1-x-x^2)) )); // G. C. Greubel, May 24 2019
(Sage) a=(x^3*(1-3*x^2+2*x^3-x^4)/((1+x)*(1-3*x+x^2)^2*(1-x-x^2)) ).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, May 24 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 05 2006
STATUS
approved