|
Search: id:A097100
|
|
|
| A097100 |
|
Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n containing k subwords of the type U H^j U or D H^j D for some j>0, where U=(1,1), H=(1,0) and D=(1,-1) (can be easily expressed using RNA secondary structure terminology). |
|
+0
1
|
|
| 1, 1, 1, 2, 4, 8, 15, 2, 28, 8, 1, 53, 24, 5, 102, 62, 21, 199, 152, 68, 4, 391, 366, 196, 24, 1, 773, 868, 531, 104, 7, 1537, 2032, 1393, 368, 43, 3075, 4694, 3593, 1172, 195, 6, 6189, 10732, 9120, 3528, 754, 48, 1, 12525, 24348, 22822, 10224, 2632, 272, 9
(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*G*[z+(1-z+t*z)^2*(G-zG-1)]/(1-z).
|
|
EXAMPLE
|
Triangle starts:
1;
1;
1;
2;
4;
8;
15,2;
28,8,1;
53,24,5;
It seems that, except for the first 3 rows, rows 4n-1, 4n, 4n+1 have 2n-1 terms and rows 4n+2 have 2n terms (n=1,2,...).
T(8,2)=5 because we have (UHU)H(DHD)H, (UHU)HH(DHD), H(UHU)H(DHD), (UHHU)H(DHD) and (UHU)H(DHHD); the required subwords are shown between parentheses.
|
|
CROSSREFS
|
Cf. A004148.
Sequence in context: A118869 A118897 A098056 this_sequence A002954 A019278 A084345
Adjacent sequences: A097097 A097098 A097099 this_sequence A097101 A097102 A097103
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 15 2004
|
|
|
Search completed in 0.002 seconds
|
