A110298 - OEIS

%I #14 Jan 04 2023 02:58:13

%S 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,

%T 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,

%U 37,34,32,32,34,37,82,185,978,0,185,82,74,68,64,68,74,82,185,423

%N 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.

%H G. C. Greubel, <a href="/A110298/b110298.txt">Rows n = 1..50 of the triangle, flattened</a>

%H W. R. Schmitt and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0166-218X(92)00038-N">Linear trees and RNA secondary structure</a>, Discrete Appl. Math., 51, 317-323, 1994.

%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1978), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

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

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

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

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

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

%e T(6,3)=2 because we have 13/2/4/5/6 and 13/2/46/5.

%e 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.

%e Triangle begins:

%e    1;

%e    1, 0;

%e    1, 0,  1;

%e    2, 0,  1, 1;

%e    4, 0,  1, 1, 2;

%e    8, 0,  2, 1, 2, 4;

%e   17, 0,  4, 2, 2, 4, 8;

%e   37, 0,  8, 4, 4, 4, 8, 17;

%e   82, 0, 17, 8, 8, 8, 8, 17, 37;

%p 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

%p 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

%t b[n_]:= b[n]= If[n==0, 1, b[n-1] +Sum[b[j]*b[n-j-2], {j, n-2}]];

%t T[n_, k_]:= If[k<3, b[n-1]*(1-(-1)^k)/2, b[k-2]*b[n-k]];

%t Table[T[n, k], {n,13}, {k,n}]//Flatten (* _G. C. Greubel_, Jan 04 2023 *)

%o (Magma)

%o 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]]) >;

%o A110298:= func< n,k | k le 2 select A004148(n-1)*(k mod 2) else A004148(k-2)*A004148(n-k) >;

%o [A110298(n,k): k in [1..n], n in [1..13]]; // _G. C. Greubel_, Jan 04 2023

%o (SageMath)

%o @CachedFunction

%o 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))

%o def A110298(n, k):

%o     if (k<3): return b(n-1)*(k%2)

%o     else: return b(k-2)*b(n-k)

%o flatten([[A110298(n,k) for k in range(1,n+1)] for n in range(1,11)]) # _G. C. Greubel_, Jan 04 2023

%Y Cf. A004148.

%K nonn,tabl

%O 1,7

%A _Emeric Deutsch_, Jul 18 2005