A176006 The number of branching configurations of RNA (see Sankoff, 1985) with n or fewer hairpins.

1, 2, 4, 10, 32, 122, 516, 2322, 10880, 52466, 258564, 1296282, 6589728, 33887466, 175966212, 921353250, 4858956288, 25786112994, 137604139012, 737922992938, 3974647310112, 21493266631002, 116642921832964, 635074797251890

Offset

0,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]

Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.

David Sankoff, Simultaneous solution of the RNA folding, alignment and protosequence problems, SIAM J. Appl. Math 45(5) (1985), 810-825.

David Sankoff, Simultaneous solution of the RNA folding, alignment and protosequence problems, SIAM J. Appl. Math 45(5) (1985), 810-825.

Formula

G.f.: (3 - x - sqrt(1 - 6*x + x^2))/(2*(1 - x)).

Conjecture : n*a(n) +(9-7*n)*a(n-1) +(7*n-12)*a(n-2) +(3-n)*a(n-3)=0. - R. J. Mathar, Jul 24 2012

a(n) ~ 2^(1/4)*(3 + 2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012

Example

For n = 3, the a(3) = 10 branching configurations with 3 or fewer hairpins are: unfolded, (), ()(), (()()), ()()(), (()())(), ()(()()), (()()()), ((()())()), and (()(()())).

Mathematica

CoefficientList[Series[(3-x-Sqrt[1-6*x+x^2])/(2*(1-x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)

Prog

(PARI) my(x='x+O('x^50)); Vec((3-x-sqrt(1-6*x+x^2))/(2*(1-x))) \\ G. C. Greubel, Mar 22 2017

Crossrefs

The cumulative sums of A155069.

Sequence in context: A120017 A000736 A263663 * A263664 A263665 A001250

Adjacent sequences: A176003 A176004 A176005 * A176007 A176008 A176009

Keyword

easy,nonn

Author

Lee A. Newberg, Apr 05 2010

Status

approved