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(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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 18 2005
STATUS
approved