login
Number of irreducible chord diagrams with 2n nodes.
(Formerly M3618 N1468)
79

%I M3618 N1468 #198 Aug 31 2024 11:09:56

%S 1,1,1,4,27,248,2830,38232,593859,10401712,202601898,4342263000,

%T 101551822350,2573779506192,70282204726396,2057490936366320,

%U 64291032462761955,2136017303903513184,75197869250518812754,2796475872605709079512,109549714522464120960474,4509302910783496963256400,194584224274515194731540740

%N Number of irreducible chord diagrams with 2n nodes.

%C Perturbation expansion in quantum field theory: spinor case in 4 spacetime dimensions.

%C a(n)*2^(-n) is the coefficient of the x^(2*n-1) term in the series reversal of the asymptotic expansion of 2*DawsonF(x) = sqrt(Pi)*exp(-x^2)*erfi(x) for x -> inf. - _Vladimir Reshetnikov_, Apr 23 2016

%C The September 2018 talk by _Noam Zeilberger_ (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - _N. J. A. Sloane_, Sep 17 2018

%C A set partition is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y. Then a(n) is the number of topologically connected 2-uniform set partitions of {1...2n}. See my links for examples. - _Gus Wiseman_, Feb 23 2019

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A000699/b000699.txt">Table of n, a(n) for n = 0..404</a> (terms up to n=100 from T. D. Noe)

%H S. Belinschi, M. Bozejko, F. Lehner, and R. Speicher, <a href="https://arxiv.org/abs/0910.4263">The normal distribution is "boxplus"-infinitely divisible</a>, arXiv:0910.4263 [math.OA], 2009-2010.

%H Daniel J. Bernstein, S. Engels, T. Lange, R. Niederhagen, et al., <a href="https://cr.yp.to/dlog/sect113r2-20160806.pdf">Faster elliptic-curve discrete logarithms on FPGAs</a>, Preprint, 2016.

%H Michael Borinsky, <a href="https://arxiv.org/abs/1603.01236">Generating asymptotics for factorially divergent sequences</a>, arXiv preprint arXiv:1603.01236 [math.CO], 2016.

%H Michael Borinsky, <a href="https://doi.org/10.37236/5999">Generating asymptotics for factorially divergent sequences</a>, El. J. Combin. 25 (2018) P4.1, Sect 7.1.

%H Michael Borinsky, Gerald V. Dunne, and Karen Yeats, <a href="https://www.arxiv.org/abs/2408.15883">Tree-tubings and the combinatorics of resurgent Dyson-Schwinger equations</a>, arXiv:2408.15883 [math-ph], 2024. See p. 9.

%H D. J. Broadhurst and D. Kreimer, <a href="http://arXiv.org/abs/hep-th/9912093">Combinatoric explosion of renormalization ...</a>, arXiv:hep-th/9912093, 1999, 2000.

%H D. J. Broadhurst and D. Kreimer, <a href="http://dx.doi.org/10.1016/S0370-2693(00)00051-4">Combinatoric explosion of renormalization tamed by Hopf algebra: 30-loop Pad-Borel resummation</a>, Phys. Lett. B 475 (2000), 63-70.

%H C. Brouder, <a href="https://arxiv.org/abs/hep-th/9906111">On the trees of quantum fields</a>, arXiv:hep-th/9906111, 1999, p. 6.

%H Jonathan Burns, <a href="http://shell.cas.usf.edu/~saito/DNAweb/SimpleAssemblyTable.txt">Assembly Graph Words - Single Transverse Component (Counts)</a>.

%H Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, <a href="https://web.archive.org/web/20191206080922/http://jtburns.myweb.usf.edu/assembly/papers/Graphs_and_DNA_Recomb_2011.pdf">Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination</a>, May 23, 2011.

%H Jonathan Burns and Tilahun Muche, <a href="http://arxiv.org/abs/1105.2926">Counting Irreducible Double Occurrence Words</a>, arXiv preprint arXiv:1105.2926 [math.CO], 2011.

%H Julien Courtiel, Karen Yeats, and Noam Zeilberger, <a href="https://arxiv.org/abs/1611.04611">Connected chord diagrams and bridgeless maps</a>, arXiv:1611.04611 [math.CO], 2016.

%H S. Dulucq, <a href="/A005819/a005819.pdf">Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots</a>, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)

%H P. Flajolet and M. Noy, <a href="http://algo.inria.fr/flajolet/Publications/FlNo00.pdf">Analytic Combinatorics of Chord Diagrams</a>, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, <a href="https://doi.org/10.1007/978-3-662-04166-6">pp. 191-201</a>.

%H M. Klazar, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00528-6">Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings</a>, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.

%H M. Klazar, <a href="http://kam.mff.cuni.cz/~klazar/evenodd.pdf">Counting even and odd partitions</a>, Amer. Math. Monthly, 110 (No. 6, 2003), 527-532.

%H Ali Assem Mahmoud, <a href="http://web.archive.org/web/20201125094355/https://uwaterloo.ca/scholar/a39mahmo/publications/aymptotics-connected-chord-diagrams">On the Asymptotics of Connected Chord Diagrams</a>, University of Waterloo (Ontario, Canada 2019).

%H Ali Assem Mahmoud, <a href="https://arxiv.org/abs/2009.12688">An Asymptotic Expansion for the Number of 2-Connected Chord Diagrams</a>, arXiv:2009.12688 [math.CO], 2020.

%H Ali Assem Mahmoud, <a href="https://arxiv.org/abs/2011.04291">Chord Diagrams and the Asymptotic Analysis of QED-type Theories</a>, arXiv:2011.04291 [hep-th], 2020.

%H Ali Assem Mahmoud, <a href="https://doi.org/10.1063/5.0171074">An asymptotic expansion for the number of two-connected chord diagrams</a>, J. Math. Phys. (2023) Vol. 64, 122301. See Example 2.1.

%H Ali Assem Mahmoud and Karen Yeats, <a href="https://arxiv.org/abs/2010.06550">Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions</a>, arXiv:2010.06550 [math.CO], 2020.

%H N. Marie, K. Yeats, <a href="https://arxiv.org/abs/1210.5457">A chord diagram expansion coming from some Dyson-Schwinger equations</a>, arXiv:1210.5457, Section 4.1.

%H Albert Nijenhuis and Herbert S. Wilf, <a href="http://dx.doi.org/10.1016/0097-3165(79)90023-2">The enumeration of connected graphs and linked diagrams</a>, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074).

%H V. Pilaud and J. Rué, <a href="http://arxiv.org/abs/1307.6440">Analytic combinatorics of chord and hyperchord diagrams with k crossings</a>, arXiv preprint arXiv:1307.6440 [math.CO], 2013.

%H J. Riordan, <a href="/A001850/a001850_2.pdf">Letter, Jul 06 1978</a>

%H E. A. Rødland, <a href="https://doi.org/10.1089/cmb.2006.13.1197">Pseudoknots in RNA Secondary Structures: Representation, Enumeration, and Prevalence</a>, J. Comput. Biology, Vol 13, No 6 (2006), 1197-1213. (see equation 10)

%H R. R. Stein, <a href="http://dx.doi.org/10.1016/0097-3165(78)90065-1">On a class of linked diagrams, I. Enumeration</a>, J. Combin. Theory, A 24 (1978), 357-366.

%H R. R. Stein and C. J. Everett, <a href="http://dx.doi.org/10.1016/0012-365X(78)90162-0">On a class of linked diagrams, II. Asymptotics</a>, Discrete Math., 21 (1978), 309-318.

%H J. Touchard, <a href="http://dx.doi.org/10.4153/CJM-1952-001-8">Sur un problème de configurations et sur les fractions continues</a>, Canad. J. Math., 4 (1952), 2-25.

%H J. Touchard, <a href="/A000698/a000698.pdf">Sur un problème de configurations et sur les fractions continues</a>, Canad. J. Math., 4 (1952), 2-25. [Annotated, corrected, scanned copy]

%H T. R. S. Walsh and A. B. Lehman, <a href="http://dx.doi.org/10.1016/0095-8956(75)90050-7">Counting rooted maps by genus. III: Nonseparable maps</a>, J. Combinatorial Theory Ser. B 18 (1975), 222-259 (nonseparable integer systems on n pairs). (Give an incorrect a(6)=2720.)

%H Gus Wiseman, <a href="/A000699/a000699.png">The a(4) = 27 connected chord diagrams</a>.

%H Gus Wiseman, <a href="/A000699/a000699_1.png">The a(5) = 248 connected chord diagrams</a>.

%H Gus Wiseman, <a href="/A000699/a000699.txt">Constructive Mathematica program for A000699</a>.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1804.10540">A theory of linear typings as flows on 3-valent graphs</a>, arXiv:1804.10540 [cs.LO], 2018.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1803.10080">A Sequent Calculus for a Semi-Associative Law</a>, arXiv:1803.10080 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).

%H Noam Zeilberger, <a href="https://vimeo.com/289907363">A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video)</a>, Rutgers Experimental Math Seminar, Sep 13 2018. Part 2 is vimeo.com/289910554.

%F a(n) = (n-1)*Sum_{i=1..n-1} a(i)*a(n-i) for n > 1, with a(1) = a(0) = 1. [Modified to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020]

%F A212273(n) = n * a(n). - _Michael Somos_, May 12 2012

%F G.f. satisfies: A(x) = 1 + x + x^2*[d/dx (A(x) - 1)^2/x]. - _Paul D. Hanna_, Dec 31 2010 [Modified to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020]

%F a(n) ~ n^n * 2^(n+1/2) / exp(n+1) * (1 - 31/(24*n) - 2207/(1152*n^2) - 3085547/(414720*n^3) - 1842851707/(39813120*n^4) - ...). - _Vaclav Kotesovec_, Feb 22 2014, extended Oct 23 2017

%F G.f. A(x) satisfies: 1 = A(x) - x/(A(x) - 2*x/(A(x) - 3*x/(A(x) - 4*x/(A(x) - 5*x/(A(x) - ...))))), a continued fraction relation. - _Paul D. Hanna_, Nov 04 2020

%e a(31)=627625976637472254550352492162870816129760 was computed using Kreimer's Hopf algebra of rooted trees. It subsumes 2.6*10^21 terms in quantum field theory.

%e G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 27*x^4 + 248*x^5 + 2830*x^6 +...

%e where d/dx (A(x) - 1)^2/x = 1 + 4*x + 27*x^2 + 248*x^3 + 2830*x^4 +...

%p A000699 := proc(n)

%p option remember;

%p if n <= 1 then

%p 1;

%p else

%p add((2*i-1)*procname(i)*procname(n-i),i=1..n-1) ;

%p end if;

%p end proc:

%p seq(A000699(n),n=0..30) ; # _R. J. Mathar_, Jun 12 2018

%t terms = 22; A[_] = 0; Do[A[x_] = x + x^2 * D[A[x]^2/x, x] + O[x]^(terms+1) // Normal, terms]; CoefficientList[A[x], x] // Rest (* _Jean-François Alcover_, Apr 06 2012, after _Paul D. Hanna_, updated Jan 11 2018 *)

%t a = ConstantArray[0,20]; a[[1]]=1; Do[a[[n]] = (n-1)*Sum[a[[i]]*a[[n-i]],{i,1,n-1}],{n,2,20}]; a (* _Vaclav Kotesovec_, Feb 22 2014 *)

%t Module[{max = 20, s}, s = InverseSeries[ComplexExpand[Re[Series[2 DawsonF[x], {x, Infinity, 2 max + 1}]]]]; Table[SeriesCoefficient[s, 2 n - 1] 2^n, {n, 1, max}]] (* _Vladimir Reshetnikov_, Apr 23 2016 *)

%o (PARI) {a(n)=local(A=1+x*O(x^n)); for(i=1, n, A=1+x+x^2*deriv((A-1)^2/x)+x*O(x^n)); polcoeff(A, n)} \\ _Paul D. Hanna_, Dec 31 2010 [Modified to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020]

%o (PARI) {a(n) = my(A); A = 1+O(x) ; for( i=0, n, A = 1+x + (A-1)*(2*x*A' - A + 1)); polcoeff(A, n)}; /* _Michael Somos_, May 12 2012 [Modified to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020] */

%o (PARI)

%o seq(N) = {

%o my(a = vector(N)); a[1] = 1;

%o for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;

%o };

%o seq(22) \\ _Gheorghe Coserea_, Jan 22 2017

%o (Python)

%o def A000699_list(n):

%o list = [1, 1] + [0] * (n - 1)

%o for i in range(2, n + 1):

%o list[i] = (i - 1) * sum(list[j] * list[i - j] for j in range(1, i))

%o return list

%o print(A000699_list(22)) # _M. Eren Kesim_, Jun 23 2021

%Y Sequences mentioned in the _Noam Zeilberger_ 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.

%Y Cf. A004300, A051862, A212273. Column sums of A232223. First column of A322402.

%Y Cf. A007297, A016098, A099947, A136653, A268815, A306438, A324166, A324172, A324173, A324327.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _David Broadhurst_, Dec 14 1999

%E Inserted "chord" in definition. - _N. J. A. Sloane_, Jan 19 2017

%E Added a(0)=1. - _N. J. A. Sloane_, Nov 05 2020

%E Modified formulas slightly to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020