OFFSET
0,12
LINKS
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
FORMULA
T(n,k) = (k+1)T(n-k, 0) for k < n; T(n,n) = 1. T(n,0) = a(n)-2a(n-1) + a(n-2) (n >= 2), where a(n) = Sum_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k, n-k+1)/k = A004148(n).
G.f.: 1/(1-tz) + (1-z)(g-1-zg)/(1-tz)^2, where g = (1 - z + z^2 - sqrt(1 - 2z - z^2 - 2z^3 + z^4))/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).
EXAMPLE
Triangle starts:
1;
0, 1;
0, 0, 1;
1, 0, 0, 1;
1, 2, 0, 0, 1;
2, 2, 3, 0, 0, 1;
5, 4, 3, 4, 0, 0, 1;
Row n has n+1 terms.
T(6,3)=4 because we have (HHH)UHD, (HH)UHD(H), (H)UHD(HH) and UHD(HHH), where U=(1,1), H=(1,0) and D=(1,-1); the 3 required level steps are shown between parentheses.
MAPLE
a:=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<0 then 0 elif k<n-1 then (k+1)*(a(n-k)-2*a(n-k-1)+a(n-k-2)) elif k=n-1 then 0 elif k=n then 1 else 0 fi end: seq(seq(T(n, k), k=0..n), n=0..12); # yields the sequence in linear form: a:=proc(n) if n=0 then 1 else sum(binomial(k, n-k)*binomial(k, n-k+1)/k, k=ceil((n+1)/2)..n) fi end: T:=proc(n, k) if k<0 then 0 elif k<n-1 then (k+1)*(a(n-k)-2*a(n-k-1)+a(n-k-2)) elif k=n-1 then 0 elif k=n then 1 else 0 fi end: TT:=(n, k)->T(n-1, k-1): matrix(13, 13, TT); # yields the sequence in matrix form:
MATHEMATICA
(* c is A004148 *)
c[n_] := c[n] = If[n == 0, 1, c[n-1] + Sum[c[k]*c[n-2-k], {k, n-2}]];
T[n_, k_] := T[n, k] = Which[k < 0, 0, k < n-1, (k+1)*(c[n-k] - 2*c[n-k-1] + c[n-k-2]), k == n-1, 0, k == n, 1, True, 0];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 30 2024 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Sep 15 2004
STATUS
approved