|
%I #10 Jul 24 2022 11:06:36
%S 1,4,12,34,92,242,627,1608,4096,10388,26269,66304,167161,421162,
%T 1060816,2671908,6730941,16961430,42758695,107843080,272136858,
%U 687106696,1735849310,4387895300,11098372185,28088028612,71128006458,180224822694
%N Number of valleys (i.e., (1,-1) followed by (1,1)) at level zero in all peakless Motzkin paths of length n+6 (can be easily translated into RNA secondary structure terminology).
%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="http://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
%F a(n) = Sum_{k>=0} k*A110333(n+6,k).
%F G.f.: 8/((1 - z + z^2 + Q)^2*(1 - 2z - z^2 + z^4 + (1 - z - z^2)Q)), where Q = sqrt(1 - 2z - z^2 - 2z^3 + z^4).
%F D-finite with recurrence +(n+10)*(79*n+56)*a(n) +(79*n^2+300*n-6319)*a(n-1) +12*(-65*n^2-383*n+259)*a(n-2) +(59*n^2-330*n-1751)*a(n-3) +6*(-28*n^2-83*n-301)*a(n-4) +(691*n^2+666*n-343)*a(n-5) -(227*n+280)*(n-2)*a(n-6)=0. - _R. J. Mathar_, Jul 24 2022
%e a(1)=4 because among the 37 (=A004148(7)) peakless Motzkin paths of length 7 only HUH(DU)HD, UH(DU)HDH, UH(DU)HHD and UHH(DU)HD have valleys at level zero (shown between parentheses; here U=(1,1), H=(1,0), D=(1,-1)).
%p Q:=sqrt(1-2*z-z^2-2*z^3+z^4): G:=8/(1-z+z^2+Q)^2/(1-2*z-z^2+z^4+(1-z-z^2)*Q): Gser:=series(G,z=0,34): 1,seq(coeff(Gser,z^n),n=1..31);
%Y Cf. A004148, A110333.
%K nonn
%O 0,2
%A _Emeric Deutsch_, Jul 20 2005
|
