OFFSET
0,7
COMMENTS
Also, triangle read by rows: T(n,k) (0<=k<=floor(n/3)) is the number of RNA secondary structures of size n (i.e. with n nodes) having k arcs that are not covered by other arcs. E.g. T(5,1)=7 because we have (13)/2/4/5, (14)/2/3/5, (15)/2,3,4, 1/(24),3,5, 1/(25)/3/4, 1/2/(35)/4 and (15)/24/3; T(6,2)=1 because we have (13)/2/(46)/5 (the arcs that are not covered by other arcs are shown between parentheses).
Row n has 1+floor(n/3) terms. Sum(k*T(n,k),k=0..floor(n/3))=A089737(n-3) for n>=3.
LINKS
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
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 at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.
M. S. Waterman, Home Page (contains copies of his papers)
FORMULA
G.f.: 2/[2-t-2z+tz+tz^2+tsqrt(1-2z-z^2-2z^3+z^4)].
Columns k=0, 1, 2, ... have g.f.: z^(2k)*(g-1)^k/(1-z)^(k+1), where g=(1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4))/(2z^2) is the g.f. of A004148.
G.f.: 1/[1-z-tz^2*(g-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(7,2)=5 because we have UHDUHDH, UHDHUHD, HUHDUHD, UHHDUHD, UHDUHHD, where U=(1,1), D=(1,-1) and H=(1,0) (in these paths all U's start at level zero).
Triangle begins
1;
1;
1;
1,1;
1,3;
1,7;
1,15,1;
1,31,5;
MAPLE
g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=simplify(1/(1-z-t*z^2*(g-1))): Gser:=simplify(series(G, z=0, 22)): P[0]:=1: for n from 1 to 18 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 18 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/3)) od;
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 07 2004, Jul 19 2005
EXTENSIONS
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007
STATUS
approved