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
Keywords
Examples
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) ).
Links
- 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.
Programs
-
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);
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
Comments