A097107 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and containing a total of k level steps H in all DHH...HU's, where U=(1,1), H=(1,0) and D=(1,-1) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 17, 36, 1, 77, 4, 1, 167, 13, 4, 1, 365, 40, 13, 4, 1, 805, 114, 41, 13, 4, 1, 1790, 314, 119, 42, 13, 4, 1, 4008, 845, 335, 124, 43, 13, 4, 1, 9033, 2230, 925, 356, 129, 44, 13, 4, 1, 20477, 5809, 2506, 1006, 377, 134, 45, 13, 4, 1, 46663, 14980, 6712

Offset

0,4

Comments

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

Links

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

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, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Formula

G.f.: G=G(t, z) satisfies G=1+zG+z^2*(G-1)[(1-z)G+z(1-t)/(1-z)]/(1-tz).

Example

Triangle starts:
1;
1;
1;
2;
4;
8;
17;
36,1;
77,4,1;
167,13,4,1;
Row n>=6 contains n-5 terms.
T(10,3)=4 because we have UHD(HHH)UHDH, UHD(HHH)UHHD, HUHD(HHH)UHD and UHHD(HHH)UHD, where U=(1,1), H=(1,0) and D=(1,-1); the 3 required H's are shown between parentheses.

Crossrefs

Cf. A004148.

Sequence in context: A127680 A136750 A274115 * A098083 A182900 A202843

Adjacent sequences: A097104 A097105 A097106 * A097108 A097109 A097110

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 16 2004

Status

approved