A098056 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k subwords of the type uh^ju, dH^jd, or dh^ju for some j>0, where u=(1,1), d=(1,-1) and h=(1,0) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 15, 2, 27, 9, 1, 48, 29, 5, 84, 80, 21, 147, 198, 74, 4, 257, 463, 230, 27, 1, 451, 1033, 667, 125, 7, 796, 2235, 1811, 488, 43, 1413, 4727, 4694, 1676, 219, 6, 2526, 9828, 11700, 5317, 946, 54, 1, 4544, 20192, 28252, 15813, 3696, 326, 9, 8226, 41100

Offset

0,4

Comments

Row n

Row sums are the RNA secondary structure numbers (A004148).

A098056(n,0)=A098057(n).

Sum(k*A098056(n,k),k>=0)=A187259(n).

References

I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1979, 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Links

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

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.

Formula

G.f.=G=G(t, z) satisfies G = 1 + zG + z^2*[H + 2tzH/(1-z)+t^2*z^2*H/(1-z)^2+ z/(1-z)][G-(1-t)zH/(1-z)^2], where H=(1-z)^2*G-1+z.

The 4-variate g.f. G(t,s,v,z) of peakless Motzkin paths, where t, s, v mark subwords of the types uH^ju, dH^jd, dH^ju, respectively, and z marks length, satisfies the equation

G = 1+zG+z^2*[H + (t+s)zH/(1-z)+tsz^2*H/(1-z)^2+z/(1-z)][G-(1-v)zH/(1-z)^2],

where H = (1-z)[(1-z)G-1]. As special cases we get the current sequence A098056 and the sequences A097777 and A098083.

Example

Triangle starts:
1;
1;
1;
2;
4;
8;
15,2;
27,9,1;
48,29,5;
84.80,21;
147,198,74,7;
It seems that the number r(n) of terms in row n>=3 is given by r(n)=n/2-1 if
n=2 (mod 4) and r(n)=2*round(n/4)-1 otherwise (here round(m) is the nearest integer to m).
T(7,1)=9 because we have h(uhu)hdd, (uhhu)hdd, (uhu)hhdd, (uhu)hddh, uh(dhu)hd and the reflections of the first four paths in a vertical axis; here u=(1,1), h=(1,0), d=(1,-1) and the pertinent subwords are shown between parentheses.

Crossrefs

Cf. A041048, A098057, A187259.

Sequence in context: A118890 A118869 A118897 * A097100 A002954 A019278

Adjacent sequences: A098053 A098054 A098055 * A098057 A098058 A098059

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 11 2004r

Status

approved