cp's OEIS Frontend

A089741 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k UHH...HD's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

%I A089741 #16 Jan 13 2025 09:36:46
%S A089741 1,1,1,1,1,1,3,1,7,1,15,1,1,31,5,1,63,18,1,127,56,1,1,255,160,7,1,511,
%T A089741 432,34,1,1023,1120,138,1,1,2047,2816,500,9,1,4095,6912,1672,55,1,
%U A089741 8191,16640,5264,275,1,1,16383,39424,15808,1205,11,1,32767,92160,45696,4797
%N A089741 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k UHH...HD's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).
%H A089741 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 A089741 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 A089741 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 A089741 G.f.: (1-2*z+2*z^2-t*z^3-sqrt((1-t*z^3)*(1-4*z+4*z^2-t*z^3)))/(2*z^2*(1-z)).
%e A089741 T(7,2)=5 because we have H(UHD)(UHD), (UHD)H(UHD), (UHD)(UHD)H, (UHD)(UHHD) and (UHHD)(UHD) (the required subwords are shown between parentheses).
%e A089741 Triangle begins:
%e A089741   1;
%e A089741   1;
%e A089741   1;
%e A089741   1,   1;
%e A089741   1,   3;
%e A089741   1,   7;
%e A089741   1,  15,   1;
%e A089741   1,  31,   5;
%e A089741   1,  63,  18;
%e A089741   1, 127,  56,   1;
%e A089741   1, 255, 160,   7;
%e A089741   ...
%Y A089741 Row sums yield A004148. Column 1 is A000225, column 2 is A001793.
%K A089741 nonn,tabf
%O A089741 0,7
%A A089741 _Emeric Deutsch_, Jan 08 2004