|
Search: id:A098056
|
|
|
| A098056 |
|
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k subwords of the type U H^j U, D H^j D, or D H^j U for some j>0, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology). |
|
+0
1
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
Row sums are the RNA secondary structure numbers (A004148).
|
|
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
|
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.
|
|
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 h(n) of terms in row n>=3 is given by h(n)=n/2-1 if
n=2 (mod 4) and h(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.
Sequence in context: A118890 A118869 A118897 this_sequence A097100 A002954 A019278
Adjacent sequences: A098053 A098054 A098055 this_sequence A098057 A098058 A098059
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 11 2004
|
|
|
Search completed in 0.002 seconds
|
