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

%I #32 Jul 26 2020 18:54:27

%S 1,2,4,10,32,122,516,2322,10880,52466,258564,1296282,6589728,33887466,

%T 175966212,921353250,4858956288,25786112994,137604139012,737922992938,

%U 3974647310112,21493266631002,116642921832964,635074797251890

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

%H Vincenzo Librandi, <a href="/A176006/b176006.txt">Table of n, a(n) for n = 0..200</a>

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H David Sankoff, <a href="https://doi.org/10.1137/0145048">Simultaneous solution of the RNA folding, alignment and protosequence problems</a>, SIAM J. Appl. Math 45(5) (1985), 810-825.

%H David Sankoff, <a href="https://pdfs.semanticscholar.org/7ce8/d1231c8c00ddc36de23aaf4cf1225a130f3e.pdf?_ga=2.152919417.1954741913.1595406974-1181019897.1595406974">Simultaneous solution of the RNA folding, alignment and protosequence problems</a>, SIAM J. Appl. Math 45(5) (1985), 810-825.

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

%F 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

%F a(n) ~ 2^(1/4)*(3 + 2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 20 2012

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

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

%o (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

%Y The cumulative sums of A155069.

%K easy,nonn

%O 0,2

%A _Lee A. Newberg_, Apr 05 2010