login
Number of blocks in all RNA secondary structures with n nodes (an RNA secondary structure can be viewed as a restricted noncrossing partition).
17

%I #48 Nov 14 2022 20:02:52

%S 1,2,5,13,32,80,201,505,1273,3217,8146,20668,52531,133726,340909,

%T 870213,2223958,5689807,14571335,37350585,95821071,246015677,

%U 632088930,1625119218,4180845277,10762096850,27718352411,71426753423,184146711578

%N Number of blocks in all RNA secondary structures with n nodes (an RNA secondary structure can be viewed as a restricted noncrossing partition).

%C Antidiagonal sums of A132812. - _Philippe Deléham_, Jun 08 2013

%H G. C. Greubel, <a href="/A110320/b110320.txt">Table of n, a(n) for n = 1..1000</a>

%H Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2211.04914">Grand Dyck paths with air pockets</a>, arXiv:2211.04914 [math.CO], 2022.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.

%H 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 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 M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.emis.de/journals/SLC/opapers/s08viennot.pdf">Polynomes 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 G.f.: (1-z-z^2)/(2*z^2*sqrt(1-2*z-z^2-2*z^3+z^4))-1/(2*z^2).

%F a(n) = Sum_{k=1..n} k*A110319(n,k).

%F Conjecture: a(n) = (A051292(n+2)-A051286(n+1))/2. - _Gerald McGarvey_, Jan 14 2007

%F a(n) = (A051286(n+2)-A051286(n+1)-A051286(n))/2. - _Benedict W. J. Irwin_, Sep 24 2016

%F a(n) ~ sqrt(4 + 9/sqrt(5)) * (3+sqrt(5))^n / (sqrt(Pi*n) * 2^(n+1)). - _Vaclav Kotesovec_, Sep 25 2016, equivalently, a(n) ~ phi^(2*n + 3) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 06 2021

%F D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(n-7)*a(n-3) +2*(2*n-3)*a(n-4) +(n-5)*a(n-5) +(-n+4)*a(n-6)=0. - _R. J. Mathar_, Feb 21 2020

%e a(4)=13 because the 4 (=A004148(4)) RNA secondary structures of size 4, namely 1/2/3/4, 13/2/4, 14/2/3 and 1/24/3, have altogether 4+3+3+3=13 blocks.

%p G:=1/2*(1-z-z^2)/z^2/(1-2*z-z^2-2*z^3+z^4)^(1/2)-1/2*1/(z^2): Gser:=series(G,z=0,37): seq(coeff(Gser,z^n),n=1..33);

%t Table[Sum[Binomial[n-j+1,j]Binomial[n-j+1,j-1],{j, 0, n}],{n,1,25}] (* _Benedict W. J. Irwin_, Sep 24 2016 *)

%Y Cf. A004148, A110319.

%K nonn

%O 1,2

%A _Emeric Deutsch_, Jul 19 2005