A110320 Number of blocks in all RNA secondary structures with n nodes (an RNA secondary structure can be viewed as a restricted noncrossing partition).
1, 2, 5, 13, 32, 80, 201, 505, 1273, 3217, 8146, 20668, 52531, 133726, 340909, 870213, 2223958, 5689807, 14571335, 37350585, 95821071, 246015677, 632088930, 1625119218, 4180845277, 10762096850, 27718352411, 71426753423, 184146711578
Offset: 1
Keywords
Examples
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.
Links
- G. C. Greubel, Table of n, a(n) for n = 1..1000
- Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
- Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
- Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
- W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
- P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
- M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problèmes d'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
Programs
-
Maple
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);
-
Mathematica
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 *)
Formula
G.f.: (1-z-z^2)/(2*z^2*sqrt(1-2*z-z^2-2*z^3+z^4))-1/(2*z^2).
a(n) = Sum_{k=1..n} k*A110319(n,k).
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
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
Comments