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,4

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

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

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 *)

Prog

(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

Crossrefs

Column k=0 of A217876.

Column k=1 of A239144.

Sequence in context: A053732 A216617 A243412 * A119495 A148301 A339039

Adjacent sequences: A170938 A170939 A170940 * A170942 A170943 A170944

Keyword

nonn,easy

Author

Barry Cipra, Feb 09 2010

Extensions

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

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

Status

approved