cp's OEIS Frontend

A110333 Triangle read by rows: T(n,k) (n,k>=0) = number of peakless Motzkin paths of length n having k valleys (i.e., (1,-1) followed by (1,1)) at level zero (can be easily translated into RNA secondary structure terminology).

%I A110333 #13 Jul 23 2017 02:44:23
%S A110333 1,1,1,2,4,8,16,1,33,4,70,12,152,32,1,336,82,5,754,206,18,1714,512,56,
%T A110333 1,3940,1264,163,6,9145,3109,456,25,21406,7634,1243,88,1,50478,18737,
%U A110333 3326,284,7,119814,46006,8781,868,33,286045,113062,22955,2556,129,1,686456
%N A110333 Triangle read by rows: T(n,k) (n,k>=0) = number of peakless Motzkin paths of length n having k valleys (i.e., (1,-1) followed by (1,1)) at level zero (can be easily translated into RNA secondary structure terminology).
%C A110333 Row n (n >= 3) has floor(n/3) terms.
%C A110333 Row sums yield the RNA secondary structure numbers (A004148).
%H A110333 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 A110333 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 A110333 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 A110333 T(n,0) = A110334(n).
%F A110333 Sum_{k>=0} k*T(n,k) = A110335(n-6) for n >= 6, 0 otherwise.
%F A110333 G.f.: (1 + z^2*g - tz^2*g - z^2 + tz^2)/(1 - z - z^3*g - tz^2*g + tz^3*g + z^3 + tz^2 - tz^3), where g = 1 + zg + z^2*g(g-1) = (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).
%e A110333 T(10,2)=5 because we have HUH(DU)H(DU)HD, UH(DU)H(DU)HDH, UHH(DU)H(DU)HD, UH(DU)HH(DU)HD and UH(DU)H(DU)HHD, where U=(1,1), H=(1,0), D=(1,-1) and the valleys at level zero are shown between parentheses.
%e A110333 Triangle begins:
%e A110333     1;
%e A110333     1;
%e A110333     1;
%e A110333     2;
%e A110333     4;
%e A110333     8;
%e A110333    16,  1;
%e A110333    33,  4;
%e A110333    70, 12;
%e A110333   152, 32,  1;
%e A110333   336, 62,  5;
%p A110333 g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=(1+z^2*g-z^2*g*t-z^2+t*z^2)/(1-z-z^3*g-t*z^2*g+t*z^3*g+z^3+t*z^2-t*z^3): Gser:=simplify(series(G,z=0,23)): P[0]:=1: for n from 1 to 20 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 2 do print(1) od: for n from 3 to 20 do seq(coeff(t*P[n],t^k),k=1..floor(n/3)) od; # yields sequence in triangular form
%Y A110333 Cf. A004148, A110334, A110335.
%K A110333 nonn,tabf
%O A110333 0,4
%A A110333 _Emeric Deutsch_, Jul 20 2005
%E A110333 Keyword tabf added by _Michel Marcus_, Apr 09 2013