|
%I #10 Jul 24 2022 11:04:46
%S 1,1,1,2,4,8,16,33,70,152,336,754,1714,3940,9145,21406,50478,119814,
%T 286045,686456,1655053,4007131,9738812,23750895,58106547,142569506,
%U 350738607,864980279,2138034715,5295877279,13143521437,32679745904
%N 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).
%C Column 0 of A110333.
%H W. R. Schmitt and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0166-218X(92)00038-N">Linear trees and RNA secondary structure</a>, Discrete Appl. Math., 51, 317-323, 1994.
%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1978), 261-272.
%H M. Vauchassade de Chaumont and G. Viennot, <a href="https://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
%F 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).
%F 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
%e 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) ).
%p 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);
%Y Cf. A004148, A110333.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Jul 20 2005
|
