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

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

Links

Table of n, a(n) for n=0..55.

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.

Formula

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

Example

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;

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

Crossrefs

Cf. A004148, A005252, A110318.

Sequence in context: A089349 A118424 A118429 * A098073 A118390 A247294

Adjacent sequences: A110314 A110315 A110316 * A110318 A110319 A110320

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 19 2005

Status

approved