A271218 Number of symmetric linked diagrams with n links and no simple link.

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

Offset: 0

Author

Jonathan Burns, Apr 13 2016

Keywords

• nonn
• easy

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.

Examples

			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 }.
		

References

• J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.

Crossrefs

Cf. A047974, A271215.

Programs

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

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

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

Extensions

More terms from Michel Marcus, Jul 28 2020