|
| |
|
|
A271218
|
|
Number of symmetric linked diagrams with n links and no simple link.
|
|
1
|
|
|
|
1, 0, 1, 3, 12, 39, 167, 660, 3083, 13961, 70728, 355457, 1936449, 10587960, 61539129, 361182139, 2224641540, 13880534119, 90090083047, 593246514588, 4038095508691, 27905008440273, 198401618299920, 1432253086621377, 10600146578310209, 79639887325700592, 611739960145556273
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Number of symmetric chord diagrams (where reflection is equivalent) with n chords and no simple chords.
Number of symmetric assembly words that do not contain the subword aa.
|
|
|
REFERENCES
|
J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 2*a(n-1) + (2n-3)*a(n-2) - (2n-5)*a(n-3) + 2*a(n-4) - a(n-5).
a(n) = a(n-1) + 2*(n-1)*a(n-2) + a(n-3) + a(n-4) + 2*sum( k=0..n-4, a(k) ).
a(n) ~ 2^(-1/2) * e^(-5/8) * (2n/e)^(n/2) * e^( sqrt(n/2) ) (conjectured).
a(n)/a(n-1) ~ sqrt(2n) (conjectured).
a(n)/A047974(n) ~ 1/sqrt(e) (conjectured).
|
|
|
EXAMPLE
|
For n=0 the a(0)=1 solution is { ∅ }.
For n=1 there are no solutions since the link in a diagram with one link, 11, is simple.
For n=2 the a(2)=1 solution is { 1212 }.
For n=3 the a(3)=3 solutions are { 123123, 121323, 123231 }.
For n=4 the a(4)=12 solutions are { 12123434, 12132434, 12324341, 12314234, 12341234, 12342341, 12314324, 12341324, 12343412, 12343421, 12324143, 12342143 }.
|
|
|
MATHEMATICA
|
RecurrenceTable[{a[n]==2a[n-1]+(2n-3)a[n-2]-(2n-5)a[n-3]+2a[n-4]-a[n-5], a[0]==1, a[1]==0, a[2]==1, a[3]==3, a[4]==12}, a[n], {n, 20}]
|
|
|
PROG
|
(PARI) lista(nn) = {my(va = vector(nn)); va[1] = 1; va[2] = 0; va[3] = 1; va[4] = 3; va[5] = 12; for (n=5, nn-1, va[n+1] = 2*va[n] + (2*n-3)*va[n-1] - (2*n-5)*va[n-2] + 2*va[n-3] - va[n-4]; ); va; } \\ Michel Marcus, Jul 28 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
