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

1, 1, 1, 2, 5, 13, 37, 112, 363, 1235, 4427, 16526, 64351, 259471, 1083935, 4668704, 20732609, 94607409, 443476993, 2130346450, 10482534517, 52740593933, 271186949333, 1423127827792, 7618169603035, 41554791114643, 230857090312059, 1305086617517534

Offset: 0

Author

Barry Cipra, Feb 09 2010

Keywords

• nonn
• easy

Comments

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

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

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

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

References

• M. Nebel, Combinatorial Properties of RNA secondary Structures, 2001.
• M. Regnier, Generating Functions in Computational Biology, INRIA, March 3, 1997.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, Enumerating the number of RNA structures [See slide 8]
• Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
• I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
• P. Stadler and C. Haslinger, RNA structures with pseudo-knots: Graph theoretical and combinatorial properties, Bull. Math. Biol., Preprint 97-03-030, 1997. See Theorem 5, p. 36 for the titular recurrence.
• M. S. Waterman, Secondary structure of single-stranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.
• Eric Weisstein's World of Mathematics, Independent Edge Set
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Path Complement Graph

Crossrefs

Column k=0 of A217876.

Column k=1 of A239144.

Programs

Maple

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

Mathematica

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];
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Dec 30 2017 *)
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 *)
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 *)

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

Formula

a(n) ~ exp(sqrt(n) - n/2 - 5/4) * n^(n/2) / sqrt(2) * (1 + 31/(24*sqrt(n))). - Vaclav Kotesovec, Sep 10 2014

Extensions

More terms from R. J. Mathar, Feb 20 2010

a(0)=1 inserted and program adapted by Alois P. Heinz, Mar 10 2014