|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|