A110334 Number of peakless Motzkin paths of length n having no valleys (i.e., (1,-1) followed by (1,1)) at level zero (can be easily translated into RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 16, 33, 70, 152, 336, 754, 1714, 3940, 9145, 21406, 50478, 119814, 286045, 686456, 1655053, 4007131, 9738812, 23750895, 58106547, 142569506, 350738607, 864980279, 2138034715, 5295877279, 13143521437, 32679745904

Offset

0,4

Comments

Column 0 of A110333.

Links

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

W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Formula

G.f.: (3-z-z^2-Q)/(2-3z+z^2+z^3+zQ), where Q=sqrt(1-2z-z^2-2z^3+z^4).

D-finite with recurrence n*a(n) +(-5*n+3)*a(n-1) +2*(4*n-3)*a(n-2) +(-5*n+9)*a(n-3) +3*(n-8)*a(n-4) +6*(-n+7)*a(n-5) +2*(n-9)*a(n-6) +(n-6)*a(n-7) +3*(-n+5)*a(n-8) +(n-6)*a(n-9)=0. - R. J. Mathar, Jul 24 2022

Example

a(6)=16 because among the 17 (=A004148(6)) peakless Motzkin paths of length 6 only UH(DU)HD has a valley at level 0 (shown between parentheses; here U=(1,1), H=(1,0), D=(1,-1) ).

Maple

G:=(3-z-z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/(2-3*z+z^2+z^3+z*sqrt(1-2*z-z^2-2*z^3+z^4)): Gser:=series(G, z=0, 37): 1, seq(coeff(Gser, z^n), n=1..34);

Crossrefs

Cf. A004148, A110333.

Sequence in context: A368461 A317880 A299271 * A357904 A084636 A352044

Adjacent sequences: A110331 A110332 A110333 * A110335 A110336 A110337

Keyword

nonn

Author

Emeric Deutsch, Jul 20 2005

Status

approved