|
Search: id:A098076
|
|
|
| A098076 |
|
Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n and height k (can be easily expressed using RNA secondary structure terminology). |
|
+0
1
|
|
| 1, 1, 1, 1, 1, 1, 3, 1, 6, 1, 1, 11, 5, 1, 20, 15, 1, 1, 36, 38, 7, 1, 64, 91, 28, 1, 1, 113, 211, 89, 9, 1, 199, 477, 255, 45, 1, 1, 350, 1059, 690, 172, 11, 1, 615, 2321, 1797, 572, 66, 1, 1, 1080, 5037, 4555, 1754, 295, 13, 1, 1896, 10847, 11320, 5098, 1118, 91, 1, 1, 3328
(list; graph; listen)
|
|
|
OFFSET
|
0,7
|
|
|
COMMENT
|
Row sums are the RNA secondary structure numbers (A004148). Column 1 without the zeros yields A077855.
|
|
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. = 1+sum(t^j*z^(2j+1)/[P(j)*P(j+1)], j=0..infinity), where P(j) are polynomials in z defined by P(0)=1, P(1)=1-z, P(j)=(1-z+z^2)P(j-1)-z^2*P(j-2), j=2, 3, ....
|
|
EXAMPLE
|
Triangle starts:
1;
1;
1;
1,1;
1,3;
1,6,1;
1,11,5;
1,20,15,1;
Row n >0 has ceil(n/2) terms.
T(6,2)=5 because the peakless Motzkin paths of length 6 and height 2 are HUUHDD, UHUHDD, UUHHDD, UUHDDH, UUHDHD, where U=(1,1), H=(1,0) and D=(1,-1).
|
|
MAPLE
|
P[0]:=1: P[1]:=sort(1-z): for j from 2 to 30 do P[j]:=sort(expand((1-z+z^2)*P[j-1]-z^2*P[j-2])) od: G:=1+sum(t^i*z^(2*i+1)/P[i]/P[i+1], i=0..25): Gser:=simplify(series(G, z=0, 21)): Q[0]:=1: for m from 1 to 18 do Q[m]:=sort(coeff(Gser, z^m)) od: 1, seq(seq(coeff(t*Q[n], t^k), k=1..ceil(n/2)), n=1..16);
|
|
CROSSREFS
|
Cf. A004148, A077855.
Sequence in context: A130541 A034839 A089732 this_sequence A010287 A130270 A090049
Adjacent sequences: A098073 A098074 A098075 this_sequence A098077 A098078 A098079
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 13 2004
|
|
|
Search completed in 0.002 seconds
|
