|
%I #16 Jul 29 2020 05:39:25
%S 1,0,1,4,24,184,1911,24252,362199,6162080,117342912,2469791336,
%T 56919388745,1425435420600,38543562608825,1119188034056244,
%U 34733368101580440,1147320305439301344,40190943859500501151,1488212241729974297796,58080468361734193793551
%N Number of loop-free assembly graphs with n rigid vertices.
%C Number of chord diagrams (equivalent up to reflection) that do not contain any simple chords, e.g., 121332 contains the simple chord 33.
%D J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.
%H Kristin DeSplinter, Satyan L. Devadoss, Jordan Readyhough, and Bryce Wimberly, <a href="https://arxiv.org/abs/2007.13266">Unfolding cubes: nets, packings, partitions, chords</a>, arXiv:2007.13266 [math.CO], 2020. See Table 1 p. 15.
%F a(n) ~ (2n/e)^n / (e * sqrt(2)).
%F a(n) = (|A000806(n)| + A271218(n)) / 2.
%F a(n)/A132101(n) ~ 1/e.
%e For n=0 the a(0)=1 solution is { ∅ }.
%e For n=1, a(1)=0 since the only assembly graph with one rigid vertex is the loop 11.
%e For n=2, the a(2)=1 solution is { 1212 }.
%e For n=3, the a(3)=4 solutions are { 121323, 123123, 123231, 123132 }.
%t (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
%o (PARI) f(n) = sum(k=0, n, (2*n-k)! / (k! * (n-k)!) * (-1/2)^(n-k) ); \\ A000806
%o 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
%Y Cf. A000806, A132101, A271218.
%K nonn
%O 0,4
%A _Jonathan Burns_, Apr 13 2016
|
