A088518 Symmetric secondary structures of RNA molecules with n nucleotides.

1, 1, 1, 2, 2, 4, 5, 9, 12, 21, 29, 50, 71, 121, 175, 296, 434, 730, 1082, 1812, 2709, 4521, 6807, 11328, 17157, 28485, 43359, 71844, 109830, 181674, 278769, 460443, 708840, 1169283, 1805291, 2974574, 4604363, 7578937, 11758552, 19337489, 30064037

Offset: 0

Author

Emeric Deutsch, Nov 18 2003

Keywords

• nonn

Comments

Diagonal sums of triangle in A088855. - Philippe Deléham, Jan 04 2009

Number of prime symmetric Dyck (n+2)-paths with no ascent of length 1. E.g., the a(3) = 2 5-paths are UUUUUDDDDD and UUUDDUUDDD. - David Scambler, Aug 27 2012

a(n) is the number of 3412-avoiding involutions on [n] with no transpositions of the form (i,i+1) that are invariant under the reverse complement map. For example, a(5)=4 counts the involutions 12345, 14325, 52341, 54321. - Juan B. Gil, May 23 2020

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
• Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
• Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.

Crossrefs

Cf. A000045, A004148.

Programs

Maple

b:= proc(n) option remember;
      `if`(n=0, 1, b(n-1)+ add(b(k)*b(n-2-k), k=1..n-2))
    end:
a:= proc(n) option remember; `if`(n<2, 1,
      a(n-1) +a(n-2) +`if`(irem(n, 2, 'r')=0, -b(r-1), 0))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 27 2012

Mathematica

CoefficientList[Series[(1 - 3*x^2 + x^4 - Sqrt[1 - 2*x^2 - x^4 - 2*x^6 + x^8])/(2*x^2*(-1 + x + x^2)), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)
b[n_] := b[n] = If[n==0, 1, b[n-1] + Sum[b[k]*b[n-2-k], {k, 1, n-2}]]; a[n_] := a[n] = If[n<2, 1, a[n-1] + a[n-2] + If[{q, r} = QuotientRemainder[n, 2 ]; r==0, -b[q-1], 0]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)

Formula

G.f.: H(z) satisfies z^2*(1-z-z^2)*H^2 + (1-z-z^2)*(1+z-z^2)*H - (1+z-z^2) = 0. H = (1/(1-z-z^2))*C(-z^2/(1-3z^2+z^4)), where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function. a(0)=a(1)=1; a(2n) = a(2n-1) + a(2n-2) - A004148(n-1) for n > 0; a(2n+1) = a(2n) + a(2n-1) for n > 0.

a(n) = F(n) - Sum_{i=1..floor(n/2)-1} A004148(i)*F(n-1-2i), where F(i)=A000045(i) are the Fibonacci numbers. - Emeric Deutsch, Nov 19 2003

a(n) is asymptotic to c*phi^n/sqrt(n) where phi=(1+sqrt(5))/2 and c=0.86.... - Benoit Cloitre, Nov 19 2003

In closed form, c = sqrt(1+3/sqrt(5)) / sqrt(Pi) = 0.863346635039540133... - Vaclav Kotesovec, Mar 21 2014

D-finite with recurrence (n+2)*a(n) -a(n-1) +(-2*n-1)*a(n-2) -2*a(n-3) +(-n+3)*a(n-4) -2a(n-5) +(-2*n+13)*a(n-6) -a(n-7) +(n-8)*a(n-8)=0. - R. J. Mathar, Jul 26 2022