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,6

Links

Table of n, a(n) for n=0..32.

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

Example

a(6)=5 because we have UHHHHD, UHDUHD, UUHHDD, UHUHDD and UUHDHD, where U=(1,1), D=(1,-1) and H=(1,0).

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 *)

Crossrefs

Cf. A004148.

Sequence in context: A094981 A304969 A239812 * A319768 A366095 A354651

Adjacent sequences: A097776 A097777 A097778 * A097780 A097781 A097782

Keyword

nonn

Author

Emeric Deutsch, Sep 11 2004

Status

approved