A110335 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).
1, 4, 12, 34, 92, 242, 627, 1608, 4096, 10388, 26269, 66304, 167161, 421162, 1060816, 2671908, 6730941, 16961430, 42758695, 107843080, 272136858, 687106696, 1735849310, 4387895300, 11098372185, 28088028612, 71128006458, 180224822694
Offset: 0
Keywords
Examples
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)).
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'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
Programs
-
Maple
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);
Formula
a(n) = Sum_{k>=0} k*A110333(n+6,k).
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).
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