|
Search: id:A110333
|
|
|
| A110333 |
|
Triangle read by rows: T(n,k) (n,k>=0) = number of peakless Motzkin paths of length n having k valleys (i.e. (1,-1) followed by (1,1)) at level zero (can be easily translated into RNA secondary structure terminology). |
|
+0
3
|
|
| 1, 1, 1, 2, 4, 8, 16, 1, 33, 4, 70, 12, 152, 32, 1, 336, 82, 5, 754, 206, 18, 1714, 512, 56, 1, 3940, 1264, 163, 6, 9145, 3109, 456, 25, 21406, 7634, 1243, 88, 1, 50478, 18737, 3326, 284, 7, 119814, 46006, 8781, 868, 33, 286045, 113062, 22955, 2556, 129, 1, 686456
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
Row n (n>=3) has floor(n/3) terms. Row sums yield the RNA secondary structure numbers (A004148). T(n,0)=A110334(n). Sum(k*T(n,k), k>=0)=A110335(n-6) for n>=6 and 0 otherwise.
|
|
REFERENCES
|
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1978, 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.
|
|
FORMULA
|
G.f.= (1+z^2*g-tz^2*g-z^2+tz^2)/(1-z-z^3*g-tz^2*g+tz^3*g+z^3+tz^2-tz^3), where g=1+zg+z^2*g(g-1)=[1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4)]/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).
|
|
EXAMPLE
|
T(10,2)=5 because we have HUH(DU)H(DU)HD, UH(DU)H(DU)HDH, UHH(DU)H(DU)HD, UH(DU)HH(DU)HD and UH(DU)H(DU)HHD, where U=(1,1), H=(1,0), D=(1,-1) and the valleys at level zero are shown between parentheses.
Triangle begins:
1;
1;
1;
2;
4;
8;
16,1;
33,4;
70,12;
152,32,1;
336,62,5;
|
|
MAPLE
|
g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=(1+z^2*g-z^2*g*t-z^2+t*z^2)/(1-z-z^3*g-t*z^2*g+t*z^3*g+z^3+t*z^2-t*z^3): Gser:=simplify(series(G, z=0, 23)): P[0]:=1: for n from 1 to 20 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 2 do print(1) od: for n from 3 to 20 do seq(coeff(t*P[n], t^k), k=1..floor(n/3)) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A004148, A110334, A110335.
Sequence in context: A010745 A097777 A089738 this_sequence A069783 A102251 A036122
Adjacent sequences: A110330 A110331 A110332 this_sequence A110334 A110335 A110336
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 20 2005
|
|
|
Search completed in 0.002 seconds
|
