|
Search: id:A089742
|
|
|
| A089742 |
|
Number of subwords UHH...HD in all peakless Motzkin paths of length n+3, where U=(1,1), D=(1,-1), and H=(1,0) (can be easily expressed using RNA secondary structure terminology). |
|
+0
1
|
|
| 1, 3, 7, 17, 41, 99, 242, 596, 1477, 3681, 9215, 23155, 58368, 147530, 373768, 948882, 2413264, 6147414, 15682008, 40056238, 102434119, 262228051, 671945055, 1723350315, 4423518544, 11362907022, 29208834520, 75131251334, 193370093508
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
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. S. Waterman, Home Page (contains copies of his papers)
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^2/[(1-z)(1-z^2*g^2)], where g=(1-z+z^2-sqrt(1-2z-z^2-2*z^3+z^4))/(2z^2) is the g.f. of sequence A004148 (RNA secondary structures).
|
|
EXAMPLE
|
a(1)=3 because in the four peakless Motzkin paths of length 4, namely HHHH, H(UHD), (UHD)H, and (UHHD), we have alltogether three subwords of the required form (shown between parentheses).
|
|
CROSSREFS
|
Cf. A004148.
Sequence in context: A123335 A001333 A078057 this_sequence A131721 A058351 A086395
Adjacent sequences: A089739 A089740 A089741 this_sequence A089743 A089744 A089745
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 08 2004
|
|
|
Search completed in 0.002 seconds
|
