A170941 - OEIS

%I #50 Mar 31 2022 22:00:22

%S 1,1,1,2,5,13,37,112,363,1235,4427,16526,64351,259471,1083935,4668704,

%T 20732609,94607409,443476993,2130346450,10482534517,52740593933,

%U 271186949333,1423127827792,7618169603035,41554791114643,230857090312059,1305086617517534

%N a(n+1) = a(n) + n*a(n-1) - a(n-2) + a(n-3).

%C The number of different RNA structures for sequences of length n.

%C a(n) = number of involutions on [n] that contain no adjacent transpositions. For example, a(3) = 2 counts (in cycle form) the identity and (1,3), but not (1,2) or (2,3) because they are adjacent transpositions. - _David Callan_, Nov 11 2012

%C Conjecture: a(n)/A000085(n) -> 1/e as n -> inf. In other words, the asymptotic proportion of involutions that contain no adjacent transpositions is conjecturally = 1/e. - _David Callan_, Nov 11 2012

%C Number of matchings (i.e. Hosoya index) in the complement of P_n where P_n is the n-path graph. - _Andrew Howroyd_, Mar 15 2016

%D M. Nebel, Combinatorial Properties of RNA secondary Structures, 2001.

%D M. Regnier, Generating Functions in Computational Biology, INRIA, March 3, 1997.

%H Alois P. Heinz, <a href="/A170941/b170941.txt">Table of n, a(n) for n = 0..500</a>

%H Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, <a href="http://www.lifl.fr/SEQUOIA/Arena/Presentations/Ganjtabesh.pdf">Enumerating the number of RNA structures</a> [See slide 8]

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

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%H P. Stadler and C. Haslinger, <a href="https://doi.org/10.1006/bulm.1998.0085">RNA structures with pseudo-knots: Graph theoretical and combinatorial properties</a>, Bull. Math. Biol., Preprint 97-03-030, 1997. See Theorem 5, p. 36 for the titular recurrence.

%H M. S. Waterman, <a href="https://dornsife.usc.edu/assets/sites/516/docs/papers/msw_papers/msw-026.pdf">Secondary structure of single-stranded nucleic acids</a>, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>

%F a(n) ~ exp(sqrt(n) - n/2 - 5/4) * n^(n/2) / sqrt(2) * (1 + 31/(24*sqrt(n))). - _Vaclav Kotesovec_, Sep 10 2014

%p A170941 := proc(n) option remember; if n < 4 then [1$3,2][n+1] ; else procname(n-1)+(n-1)*procname(n-2)-procname(n-3)+procname(n-4) ; end if; end proc: seq(A170941(n), n=0..40) ; # _R. J. Mathar_, Feb 20 2010

%t a[0] = a[1] = a[2] = 1; a[3] = 2; a[n_] := a[n] = a[n-1] + (n-1) a[n-2] - a[n-3] + a[n-4];

%t Table[a[n], {n, 0, 27}] (* _Jean-François Alcover_, Dec 30 2017 *)

%t RecurrenceTable[{a[n + 1] == a[n] + n a[n - 1] - a[n - 2] + a[n - 3], a[0] == a[1] == a[2] == 1, a[3] == 2}, a, {n, 20}] (* _Eric W. Weisstein_, Apr 12 2018 *)

%t nxt[{n_,a_,b_,c_,d_}]:={n+1,b,c,d,d+(n+1)c-b+a}; NestList[nxt,{2,1,1,1,2},30][[All,2]] (* _Harvey P. Dale_, Feb 16 2020 *)

%o (PARI) a=vector(50); a[1]=a[2]=1;a[3]=2; a[4]=5; for(n=5, #a, a[n]=a[n-1]+(n-1)*a[n-2]-a[n-3]+a[n-4]); concat(1, a) \\ _Altug Alkan_, Apr 12 2018

%Y Column k=0 of A217876.

%Y Column k=1 of A239144.

%K nonn,easy

%O 0,4

%A _Barry Cipra_, Feb 09 2010

%E More terms from _R. J. Mathar_, Feb 20 2010

%E a(0)=1 inserted and program adapted by _Alois P. Heinz_, Mar 10 2014