

A170941


a(n+1) = a(n) + n*a(n1)  a(n2) + a(n3).


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 npath 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 JeanMarc 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, 207237.
P. Stadler and C. Haslinger, RNA structures with pseudoknots: Graph theoretical and combinatorial properties, Bull. Math. Biol., Preprint 9703030, 1997. See Theorem 5, p. 36 for the titular recurrence.
M. S. Waterman, Secondary structure of singlestranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167212, 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(n1)+(n1)*procname(n2)procname(n3)+procname(n4) ; 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[n1] + (n1) a[n2]  a[n3] + a[n4];
Table[a[n], {n, 0, 27}] (* JeanFranç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[n1]+(n1)*a[n2]a[n3]+a[n4]); 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



