A271215 Number of loop-free assembly graphs with n rigid vertices.

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

Table of n, a(n) for n=0..20.

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

Cf. A000806, A132101, A271218.

Sequence in context: A111556 A300736 A226738 * A135905 A239296 A028498

Adjacent sequences: A271212 A271213 A271214 * A271216 A271217 A271218

Keyword

nonn

Author

Jonathan Burns, Apr 13 2016

Status

approved