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.

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

Offset

1,7

Links

G. C. Greubel, Rows n = 1..50 of the triangle, flattened

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

T(n, 1) = A004148(n-1);

T(n, n) = A004148(n-2).

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_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k, n-k+1)/k for n >= 1).

Sum_{k=1..n} T(n, k) = A004148(n).

G.f.: 1 + t*z*g(z) + t^2*z^2*g(z)*(g(t*z) - 1), where g = 1 + z*g + z^2*g*(g-1) = (1 - z + z^2 - sqrt(1 - 2*z - z^2 - 2*z^3 + z^4))/(2*z^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;
   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;

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

Mathematica

b[n_]:= b[n]= If[n==0, 1, b[n-1] +Sum[b[j]*b[n-j-2], {j, n-2}]];
T[n_, k_]:= If[k<3, b[n-1]*(1-(-1)^k)/2, b[k-2]*b[n-k]];
Table[T[n, k], {n, 13}, {k, n}]//Flatten (* G. C. Greubel, Jan 04 2023 *)

Prog

(Magma)
A004148:= func< n | n eq 0 select 1 else (&+[Binomial(j, n-j)*Binomial(j, n-j+1)/j: j in [Ceiling((n+1)/2)..n]]) >;
A110298:= func< n, k | k le 2 select A004148(n-1)*(k mod 2) else A004148(k-2)*A004148(n-k) >;
[A110298(n, k): k in [1..n], n in [1..13]]; // G. C. Greubel, Jan 04 2023
(SageMath)
@CachedFunction
def b(n): return 1 if (n==0) else b(n-1) +sum(b(j)*b(n-j-2) for j in range(1, n-1))
def A110298(n, k):
    if (k<3): return b(n-1)*(k%2)
    else: return b(k-2)*b(n-k)
flatten([[A110298(n, k) for k in range(1, n+1)] for n in range(1, 11)]) # G. C. Greubel, Jan 04 2023

Crossrefs

Cf. A004148.

Sequence in context: A124220 A221755 A354666 * A362379 A144740 A283272

Adjacent sequences: A110295 A110296 A110297 * A110299 A110300 A110301

Keyword

nonn,tabl

Author

Emeric Deutsch, Jul 18 2005

Status

approved