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,2

Links

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

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.

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

Example

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)).

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);

Crossrefs

Cf. A004148, A110333.

Sequence in context: A349973 A107069 A191823 * A166294 A307305 A176753

Adjacent sequences: A110332 A110333 A110334 * A110336 A110337 A110338

Keyword

nonn

Author

Emeric Deutsch, Jul 20 2005

Status

approved