A097779 Number of Motzkin paths of length n, starting with an up step, ending with a down step and having no peaks (can be easily expressed using RNA secondary structure terminology).
1, 0, 0, 1, 1, 2, 5, 11, 25, 58, 135, 317, 750, 1785, 4272, 10275, 24823, 60210, 146576, 358010, 877087, 2154751, 5307166, 13102511, 32418806, 80375267, 199650310, 496803811, 1238276667, 3091173482, 7727893389, 19346109435, 48493869237
Offset: 0
Keywords
Examples
a(6)=5 because we have UHHHHD, UHDUHD, UUHHDD, UHUHDD and UUHDHD, where U=(1,1), D=(1,-1) and H=(1,0).
Crossrefs
Cf. A004148.
Programs
-
Maple
G:=z+1/2*(1-z)^2/z^2*(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4)): Gser:=series(G,z=0,40): 1,seq(coeff(Gser,z^n),n=1..37);
-
Mathematica
CoefficientList[Series[x+(1-x)^2 (1-x+x^2-Sqrt[1-2x-x^2-2x^3+x^4])/(2x^2),{x,0,40}],x] (* Harvey P. Dale, Dec 24 2016 *)
Formula
G.f. = z + (1-z)^2*[1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4)]/(2z^2)
D-finite with recurrence (n+2)*a(n) -3*n*a(n-1) +(n-4)*a(n-2) +(-n+1)*a(n-3) +3*(n-5)*a(n-4) +(-n+7)*a(n-5)=0. - R. J. Mathar, Jul 26 2022