cp's OEIS Frontend

A089732 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps (can be easily translated into RNA secondary structure terminology). Except for row 0, row n has ceiling(n/2) entries.

%I A089732 #29 Feb 01 2023 14:29:55
%S A089732 1,1,1,1,1,1,3,1,6,1,1,10,6,1,15,20,1,1,21,50,10,1,28,105,50,1,1,36,
%T A089732 196,175,15,1,45,336,490,105,1,1,55,540,1176,490,21,1,66,825,2520,
%U A089732 1764,196,1,1,78,1210,4950,5292,1176,28,1,91,1716,9075,13860,5292,336,1,1,105
%N A089732 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps (can be easily translated into RNA secondary structure terminology). Except for row 0, row n has ceiling(n/2) entries.
%H A089732 A. Panayotopoulos and P. Vlamos, <a href="http://dx.doi.org/10.1007/978-3-642-33412-2_49">Cutting Degree of Meanders</a>, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From _N. J. A. Sloane_, Dec 29 2012
%H A089732 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 A089732 Yuriy Shablya and Dmitry Kruchinin, <a href="https://arxiv.org/abs/2301.11890">Algorithms for ranking and unranking the combinatorial set of RNA secondary structures</a>, arXiv:2301.11890 [cs.DS], 2023.
%H A089732 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 A089732 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>, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
%H A089732 M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)
%F A089732 T(0, 0) = 1;
%F A089732 T(n, k) = binomial(n-k, k)*binomial(n-k, k+1)/(n-k) for 2k <= n-1.
%F A089732 G.f. = g = (1 - z + tz^2 - sqrt(1 - 2z + z^2 - 2tz^2 - 2tz^3 + t^2*z^4))/(2tz^2), solution of g = 1 + zg + tz^2*g(g-1). G.f. = 1+r(tz, z), where r(t, z) is the Narayana function defined by r = z(1+r)(1+tr). Column g.f.'s are 1/(1-z) for column 0 and z^(k+1)*N_k(z)/(1-z)^(2k+1) for columns k=1, 2, ..., where N_k(z) = (1/k)*Sum_{j=1..k} binomial(k, j)*binomial(k, j-1)*z^(j-1) are the Narayana polynomials.
%F A089732 G.f. g(z, t) = Sum_{n, k} T(n, k)z^n*t^k = 1/(1 - z + z^2*t(1-g(z, t))). - _Michael Somos_, Sep 08 2005
%F A089732 Given g.f. g(z, t) then G=z*g(z, t) series reversion in z is -G(-z, t). - _Michael Somos_, Sep 08 2005
%F A089732 Given g.f. g(z, t) then G=z*g(z, t) satisfies G = z + z*G/(1-t*z*G). - _Michael Somos_, Sep 08 2005
%e A089732 T(4,1)=3 because we have UHDH, HUHD and UHHD, where U=(1,1), D=(1,-1), H=(1,0).
%e A089732 1; 1; 1; 1,1; 1,3; 1,6,1; 1,10,6; 1,15,20,1; 1,21,50,10; 1,28,105,50,1.
%e A089732 From _Tom Copeland_, May 14 2012: (Start)
%e A089732 Or as irregular table whose diagonals are rows of A001263:
%e A089732 [1] 1;
%e A089732 [2] 1;
%e A089732 [3] 1,  1;
%e A089732 [4] 1,  3,;
%e A089732 [5] 1,  6,   1;
%e A089732 [6] 1, 10,   6;
%e A089732 [7] 1, 15,  20,  1;
%e A089732 [8] 1, 21,  50, 10;
%e A089732 [9] 1, 28, 105, 50, 1; (End)
%o A089732 (PARI) {T(n,k)=local(A); if(n<1, k==0, n--; A=1+O(x); for(i=1,(n+1)\2, A = 1/(1/(1+x*x*y*A)-x)); polcoeff(polcoeff(A,n),k))} /* _Michael Somos_, Sep 08 2005 */
%Y A089732 Row sums give A004148.
%K A089732 nonn,tabf
%O A089732 0,7
%A A089732 _Emeric Deutsch_, Jan 07 2004