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,2

Comments

Antidiagonal sums of A132812. - Philippe Deléham, Jun 08 2013

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.

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).

Conjecture: a(n) = (A051292(n+2)-A051286(n+1))/2. - Gerald McGarvey, Jan 14 2007

a(n) = (A051286(n+2)-A051286(n+1)-A051286(n))/2. - Benedict W. J. Irwin, Sep 24 2016

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

Example

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.

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 *)

Crossrefs

Cf. A004148, A110319.

Sequence in context: A255170 A255630 A298535 * A219230 A108890 A220739

Adjacent sequences: A110317 A110318 A110319 * A110321 A110322 A110323

Keyword

nonn

Author

Emeric Deutsch, Jul 19 2005

Status

approved