|
| |
|
|
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]
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
|
| |
|
|
