|
| |
|
|
A089737
|
|
Number of (1,1) steps starting at level zero in all peakless Motzkin paths of length n+3 (can be easily expressed also in RNA secondary structure terminology).
|
|
1
| |
|
|
1, 3, 7, 17, 41, 98, 235, 565, 1362, 3294, 7992, 19450, 47475, 116204, 285178, 701585, 1730003, 4275162, 10586164, 26263365, 65273566, 162499838, 405185762, 1011815774, 2530219435, 6335642377, 15884284791, 39871297479, 100194076029
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| lim(a(n)/A004148(n), n=infinity) = sqrt(5).
|
|
|
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
| a(n)=sum((5k-2n-2)binomial(k, n+1-k)*binomial(k+1, n+3-k)/[k(n+4-k)], k=ceil(n/2+1)..n+1). a(n)=A004148(n+5)-2A004148(n+4)+A004148(n+3)-A004148(n+2). G.f.=2/[1-3z+2z^2-2z^3+2z^4-z^5+(1-2z+z^2-z^3)sqrt(1-2z-z^2-2z^3+z^4)].
|
|
|
EXAMPLE
| a(2)=7 because in the eight peakless Motzkin paths of length 5, namely HHHHH, HHU'HD, HU'HHD, HU'HDH, U'HDHH, U'HHDH, U'HHHD and U'UHDD, where U=(1,1), D=(1,-1), H=(1,0), we have alltogether seven U steps starting at level zero (indicated by U').
|
|
|
CROSSREFS
| Cf. A004148.
Sequence in context: A192674 A131056 A077851 * A001333 A078057 A123335
Adjacent sequences: A089734 A089735 A089736 * A089738 A089739 A089740
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 07 2004
|
| |
|
|
