login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A170941 a(n+1) = a(n) + n*a(n-1) - a(n-2) + a(n-3). 12
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 (list; graph; refs; listen; history; text; internal format)
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]

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

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 A205544

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 01:57 EST 2019. Contains 329948 sequences. (Running on oeis4.)