|
| |
|
|
A110298
|
|
Triangle read by rows: T(n,k) (1<=k<=n) is the number of secondary structures of size n (i.e. with n nodes) for which node k is the last node in the block that contains node 1.
|
|
0
| |
|
|
1, 1, 0, 1, 0, 1, 2, 0, 1, 1, 4, 0, 1, 1, 2, 8, 0, 2, 1, 2, 4, 17, 0, 4, 2, 2, 4, 8, 37, 0, 8, 4, 4, 4, 8, 17, 82, 0, 17, 8, 8, 8, 8, 17, 37, 185, 0, 37, 17, 16, 16, 16, 17, 37, 82, 423, 0, 82, 37, 34, 32, 32, 34, 37, 82, 185, 978, 0, 185, 82, 74, 68, 64, 68, 74, 82, 185, 423, 2283, 0
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,7
|
|
|
COMMENTS
| Row sums yield A004148. T(n,1)=A004148(n-1); T(n,n)=A004148(n-2).
|
|
|
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, 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.
|
|
|
FORMULA
| T(n, 1)=b(n-1); T(n, 2)=0; T(n, k)=b(k-2)b(n-k) if k>=3, where b(n)=A004148(n) = is the number of secondary structures of size n [b(0)=1 and b(n)=sum(binomial(k, n-k)*binomial(k, n-k+1)/k, k=ceil((n+1)/2)..n) for n>=1]. G.f.=1+tzg(z)+t^2*z^2*g(z)[g(tz)-1], 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(6,3)=2 because we have 13/2/4/5/6 and 13/2/46/5.
T(15,5)=846 because on the nodes 2,3,4 we can have A004148(3)=2 secondary structures and on the nodes 6,7,...,15 we can have A004148(10)=423 secondary structures.
Triangle begins:
1;
1,0;
1,0,1;
2,0,1,1;
4,0,1,1,2;
|
|
|
MAPLE
| b:=proc(n) if n=0 then 1 else sum(binomial(j, n-j)*binomial(j, n-j+1)/j, j=ceil((n+1)/2)..n) fi end: T:=proc(n, k) if k=1 then b(n-1) elif k=2 then 0 elif k<=n then b(k-2)*b(n-k) else 0 fi end: for n from 1 to 13 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form g:=1/2/z^2*(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4)): h:=subs(z=t*z, g): G:=simplify(1+t*z*g+t^2*z^2*(h-1)*g): Gser:=simplify(series(G, z=0, 17)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser, z^n) od: for n from 1 to 13 do seq(coeff(P[n], t^k), k=1..n) od; # yields the sequence in triangular form
|
|
|
CROSSREFS
| Cf. A004148.
Sequence in context: A123226 A102210 A124220 * A144740 A049501 A102564
Adjacent sequences: A110295 A110296 A110297 * A110299 A110300 A110301
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 18 2005
|
| |
|
|
