login
A271215
Number of loop-free assembly graphs with n rigid vertices.
2
1, 0, 1, 4, 24, 184, 1911, 24252, 362199, 6162080, 117342912, 2469791336, 56919388745, 1425435420600, 38543562608825, 1119188034056244, 34733368101580440, 1147320305439301344, 40190943859500501151, 1488212241729974297796, 58080468361734193793551
OFFSET
0,4
COMMENTS
Number of chord diagrams (equivalent up to reflection) that do not contain any simple chords, e.g., 121332 contains the simple chord 33.
REFERENCES
J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.
LINKS
Kristin DeSplinter, Satyan L. Devadoss, Jordan Readyhough, and Bryce Wimberly, Unfolding cubes: nets, packings, partitions, chords, arXiv:2007.13266 [math.CO], 2020. See Table 1 p. 15.
FORMULA
a(n) ~ (2n/e)^n / (e * sqrt(2)).
a(n) = (|A000806(n)| + A271218(n)) / 2.
a(n)/A132101(n) ~ 1/e.
EXAMPLE
For n=0 the a(0)=1 solution is { ∅ }.
For n=1, a(1)=0 since the only assembly graph with one rigid vertex is the loop 11.
For n=2, the a(2)=1 solution is { 1212 }.
For n=3, the a(3)=4 solutions are { 121323, 123123, 123231, 123132 }.
MATHEMATICA
(Table[Sum[Binomial[n, i]*(2*n-i)!/2^(n-i)*(-1)^(i)/n!, {i, 0, n}], {n, 0, 20}]+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, 0, 20}])/2
PROG
(PARI) f(n) = sum(k=0, n, (2*n-k)! / (k! * (n-k)!) * (-1/2)^(n-k) ); \\ A000806
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]; ); vector(nn-1, n, (va[n] + abs(f(n-1)))/2); } \\ Michel Marcus, Jul 28 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Jonathan Burns, Apr 13 2016
STATUS
approved