This site is supported by donations to The OEIS Foundation. 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 = a = a = 1; a = 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 == a == a == 1, a == 2}, a, {n, 20}] (* Eric W. Weisstein, Apr 12 2018 *) PROG (PARI) a=vector(50); a=a=1; a=2; a=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.

Last modified June 25 11:58 EDT 2019. Contains 324352 sequences. (Running on oeis4.)