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

Author

Lee A. Newberg, Apr 05 2010

Keywords

• easy
• nonn

Comments

a(n) is the number of dissections of a convex (n+2)-sided polygon by non-intersecting diagonals such that selected least two consecutive sides of the polygon will be in the same sub-polygon. - Muhammed Sefa Saydam, Jul 02 2025

Examples

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

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.

Crossrefs

The cumulative sums of A155069.

Programs

Mathematica

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

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

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

a(n) = Sum_{x+y=n+1} A006318(x), for y >= 2, x >= -1 and A006318(-1) = 1. - Muhammed Sefa Saydam, Jul 02 2025