cp's OEIS Frontend

A097100 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n containing k subwords of the type U H^j U or D H^j D for some j>0, where U=(1,1), H=(1,0) and D=(1,-1) (can be easily expressed using RNA secondary structure terminology).

%I A097100 #10 Jan 13 2025 04:08:39
%S A097100 1,1,1,2,4,8,15,2,28,8,1,53,24,5,102,62,21,199,152,68,4,391,366,196,
%T A097100 24,1,773,868,531,104,7,1537,2032,1393,368,43,3075,4694,3593,1172,195,
%U A097100 6,6189,10732,9120,3528,754,48,1,12525,24348,22822,10224,2632,272,9
%N A097100 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n containing k subwords of the type U H^j U or D H^j D for some j>0, where U=(1,1), H=(1,0) and D=(1,-1) (can be easily expressed using RNA secondary structure terminology).
%C A097100 Row sums are the RNA secondary structure numbers (A004148).
%C A097100 T(n,0)=A190160(n).
%C A097100 Sum(k*T(n,k),k>=0)=A190161(n).
%C A097100 The generating function G=G(t,s,z) relative to the number of subwords of the form uh^bu (marked by t) and dh^bd (marked by s) for a fixed b>=1, satisfies G = 1+zG+z^2*G[z/(1-z) + (w^2+twz^b+swz^b+tsz^{2b})H], where H=(1-z)[(1-z)G-1] and w = 1/(1-z) - z^b.
%H A097100 I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.
%H A097100 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 (1979), 261-272.
%H A097100 M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08; Sem. Loth. Comb. B08l (1984) 79-86.
%F A097100 G.f.: G=G(t, z) satisfies G=1+zG+z^2*G*[z+(1-z+t*z)^2*(G-zG-1)]/(1-z).
%e A097100 Triangle starts:
%e A097100   1;
%e A097100   1;
%e A097100   1;
%e A097100   2;
%e A097100   4;
%e A097100   8;
%e A097100   15,2;
%e A097100   28,8,1;
%e A097100   53,24,5;
%e A097100   ...
%e A097100 It seems that, except for the first 3 rows, rows 4n-1, 4n, 4n+1 have 2n-1 terms and rows 4n+2 have 2n terms (n=1,2,...).
%e A097100 T(8,2)=5 because we have (UHU)H(DHD)H, (UHU)HH(DHD), H(UHU)H(DHD), (UHHU)H(DHD) and (UHU)H(DHHD); the required subwords are shown between parentheses.
%p A097100 eq := G = 1+z*G+z^2*G*(z+(1-z+t*z)^2*(G-z*G-1))/(1-z): G:= RootOf(eq,G): Gser := simplify(series(G,z=0,20)): for n from 0 to 19 do P[n] := sort(coeff(Gser,z,n)) end do: for n from 0 to 19 do seq(coeff(P[n],t,j), j=0 .. degree(P[n])) end do; # yields sequence in triangular form
%Y A097100 Cf. A004148, A190160, A190161.
%K A097100 nonn,tabf
%O A097100 0,4
%A A097100 _Emeric Deutsch_, Sep 15 2004