%I #48 Jul 26 2022 15:30:14
%S 1,1,1,2,2,4,5,9,12,21,29,50,71,121,175,296,434,730,1082,1812,2709,
%T 4521,6807,11328,17157,28485,43359,71844,109830,181674,278769,460443,
%U 708840,1169283,1805291,2974574,4604363,7578937,11758552,19337489,30064037
%N Symmetric secondary structures of RNA molecules with n nucleotides.
%C Diagonal sums of triangle in A088855. - _Philippe Deléham_, Jan 04 2009
%C 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
%C 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
%H Alois P. Heinz, <a href="/A088518/b088518.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/knight.pdf">Knight's paths towards Catalan numbers</a>, Univ. Bourgogne Franche-Comté (2022).
%H Juan B. Gil and Luiz E. Lopez, <a href="https://arxiv.org/abs/2203.10589">Enumeration of symmetric arc diagrams</a>, arXiv:2203.10589 [math.CO], 2022.
%F 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.
%F 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
%F 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
%F In closed form, c = sqrt(1+3/sqrt(5)) / sqrt(Pi) = 0.863346635039540133... - _Vaclav Kotesovec_, Mar 21 2014
%F 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
%p b:= proc(n) option remember;
%p `if`(n=0, 1, b(n-1)+ add(b(k)*b(n-2-k), k=1..n-2))
%p end:
%p a:= proc(n) option remember; `if`(n<2, 1,
%p a(n-1) +a(n-2) +`if`(irem(n, 2, 'r')=0, -b(r-1), 0))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Aug 27 2012
%t 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 *)
%t 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_ *)
%Y Cf. A000045, A004148.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Nov 18 2003