0,7

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.

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, 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.

M. S. Waterman, Home Page (contains copies of his papers)

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.

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).

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;

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;

Cf. A004148, A089737.

Sequence in context: A098093 A114712 A089741 this_sequence A094024 A061782 A074625

Adjacent sequences: A089733 A089734 A089735 this_sequence A089737 A089738 A089739

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 07 2004, Jul 19 2005

Edited by njas at the suggestion of Andrew Plewe, Jun 23 2007