login
A098050
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 UHH...HD's, 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, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 5, 2, 1, 1, 16, 11, 6, 2, 1, 1, 32, 25, 14, 7, 2, 1, 1, 64, 57, 35, 17, 8, 2, 1, 1, 128, 130, 86, 46, 20, 9, 2, 1, 1, 256, 296, 212, 119, 58, 23, 10, 2, 1, 1, 512, 672, 520, 311, 156, 71, 26, 11, 2, 1, 1, 1024, 1520, 1269, 805, 428, 197, 85, 29
OFFSET
0,7
COMMENTS
Row sums yield 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[G-1-z/(1-z)+tz/(1-tz)].
EXAMPLE
Triangle starts:
1;
1;
1;
1,1;
1,2,1;
1,4,2,1;
1,8,5,2,1;
1,16,11,6,2,1;
Row n has n-1 terms, n>=2.
T(7,3)=5 because we have U(HHH)DHH, HU(HHH)DH, HHU(HHH)D, U(H)DU(HH)D,
U(HH)DU(H)D and UU(HHH)DD, where U=(1,1), H=(1,0) and D=(1,-1); the
three pertinent H's are shown between parentheses.
CROSSREFS
Cf. A004148.
Sequence in context: A155038 A057728 A176463 * A278984 A111579 A144374
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Sep 11 2004
STATUS
approved