A110317 Triangle read by rows: T(n,k) (k>=0) is the number of RNA secondary structures of size n (i.e., with n nodes) having k arcs that are covered by other arcs.

1, 1, 1, 2, 4, 7, 1, 12, 5, 21, 15, 1, 37, 37, 8, 65, 84, 35, 1, 114, 182, 115, 12, 200, 381, 323, 73, 1, 351, 777, 825, 313, 17, 616, 1554, 1977, 1087, 138, 1, 1081, 3062, 4524, 3291, 754, 23, 1897, 5962, 9999, 9063, 3209, 241, 1, 3329, 11496, 21515, 23300

Offset: 0

Author

Emeric Deutsch, Jul 19 2005

Keywords

• nonn
• tabf

Comments

Rows 0,1,2 have one term each; row n >= 3 has ceiling(n/2) - 1 terms.

Rows sums yield A004148.

T(n,0) = A005251(n+1).

Sum_{k>=0} k*T(n,k) = A110318(n-5).

Examples

			T(6,1)=5 because we have 15/(24)/3/6, 16/(24)/3/5, 16/(25)/3/4, 16/2/(35)/4 and 1/26/(35)/4 (the covered arcs are shown between parentheses).
Triangle begins
   1;
   1;
   1;
   2;
   4;
   7,  1;
  12,  5;
  21, 15,  1;
  37, 37,  8;
		

Links

• 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, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Crossrefs

Cf. A004148, A005252, A110318.

Programs

Maple

G:=2*t/(2*t-2*z*t-1+z+t*z^2+sqrt(1-2*z-2*t*z^2+z^2-2*t*z^3+t^2*z^4)): Gser:=simplify(series(G,z=0,20)): P[0]:=1: for n from 1 to 17 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 2 do print(1) od: for n from 3 to 17 do seq(coeff(t*P[n],t^k),k=1..ceil(n/2)-1) od; # yields sequence in triangular form

Formula

G.f.: 2t/(2t - 2tz - 1 + z + tz^2 + sqrt(1 - 2z - 2tz^2 + z^2 - 2tz^3 + t^2*z^4)).