cp's OEIS Frontend

A000699 Number of irreducible chord diagrams with 2n nodes.

%I A000699 M3618 N1468 #232 Jul 01 2025 08:53:38
%S A000699 1,1,1,4,27,248,2830,38232,593859,10401712,202601898,4342263000,
%T A000699 101551822350,2573779506192,70282204726396,2057490936366320,
%U A000699 64291032462761955,2136017303903513184,75197869250518812754,2796475872605709079512,109549714522464120960474,4509302910783496963256400,194584224274515194731540740
%N A000699 Number of irreducible chord diagrams with 2n nodes.
%C A000699 Perturbation expansion in quantum field theory: spinor case in 4 spacetime dimensions.
%C A000699 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 A000699 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 A000699 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
%C A000699 From _Julien Courtiel_, Oct 09 2024: (Start)
%C A000699 a(n) is the number of rooted bridgeless combinatorial maps with n edges (genus is not fixed). A map is bridgeless if it has no edge whose removal disconnects the graph. For example, for n=2, there are 4 bridgeless maps with 2 edges: 2 planar maps with 1 vertex (either two consecutive loops, or two nested loops), 1 toric map with 1 vertex, and 1 planar map with 2 vertices connected by a double edge.
%C A000699 Also, a(n) is the number of trees with n edges equipped with a binary tubing. A tube is a connected subgraph. A binary tubing of a tree is a nested set collection S of tubes such that 1. S contains the tube of all vertices 2. Every tube of S is either reduced to one vertex, or it can be can partitioned by 2 tubes of S.
%C A000699 (End)
%D A000699 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000699 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000699 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 A000699 Serban T. Belinschi, Marek Bozejko, Franz Lehner, and Roland 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 A000699 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 A000699 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 A000699 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 A000699 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 A000699 David J. Broadhurst and Dirk Kreimer, <a href="http://arXiv.org/abs/hep-th/9912093">Combinatoric explosion of renormalization ...</a>, arXiv:hep-th/9912093, 1999, 2000.
%H A000699 David J. Broadhurst and Dirk 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 A000699 Christian 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 A000699 Jonathan Burns, <a href="http://shell.cas.usf.edu/~saito/DNAweb/SimpleAssemblyTable.txt">Assembly Graph Words - Single Transverse Component (Counts)</a>.
%H A000699 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 A000699 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 A000699 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 A000699 Serge 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 A000699 Philippe Flajolet and Marc 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 A000699 Zhen Huang, Denis Golež, Hugo U. R. Strand, and Jason Kaye, <a href="https://arxiv.org/abs/2503.19727">Automated evaluation of imaginary time strong coupling diagrams by sum-of-exponentials hybridization fitting</a>, arXiv:2503.19727 [cond-mat.str-el], 2025. See p. 21.
%H A000699 Martin 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 A000699 Martin 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 A000699 Florian Kogelbauer and Ilya Karlin, <a href="https://arxiv.org/abs/2506.17441">On the Relation of Exact Hydrodynamics to the Chapman-Enskog Series</a>, arXiv:2506.17441 [math-ph], 2025. See pp. 4-5.
%H A000699 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 A000699 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 A000699 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 A000699 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 A000699 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 A000699 Nicolas Marie and Karen Yeats, <a href="https://arxiv.org/abs/1210.5457">A chord diagram expansion coming from some Dyson-Schwinger equations</a>, arXiv:1210.5457 [math.CO], 2012, Section 4.1.
%H A000699 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 A000699 Vincent Pilaud and Juanjo 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 A000699 J. Riordan, <a href="/A001850/a001850_2.pdf">Letter, Jul 06 1978</a>
%H A000699 Einar 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 A000699 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 A000699 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 A000699 Jacques 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 A000699 Jacques 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 A000699 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 A000699 Gus Wiseman, <a href="/A000699/a000699.png">The a(4) = 27 connected chord diagrams</a>.
%H A000699 Gus Wiseman, <a href="/A000699/a000699_1.png">The a(5) = 248 connected chord diagrams</a>.
%H A000699 Gus Wiseman, <a href="/A000699/a000699.txt">Constructive Mathematica program for A000699</a>.
%H A000699 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 A000699 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 A000699 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 A000699 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 A000699 A212273(n) = n * a(n). - _Michael Somos_, May 12 2012
%F A000699 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 A000699 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 A000699 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
%F A000699 G.f. A(x) satisfies: A(x*B(x)^2) = B(x) where B(x) is the g.f. of A001147. - _Andrew Howroyd_, Nov 21 2024
%e A000699 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 A000699 G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 27*x^4 + 248*x^5 + 2830*x^6 +...
%e A000699 where d/dx (A(x) - 1)^2/x = 1 + 4*x + 27*x^2 + 248*x^3 + 2830*x^4 +...
%p A000699 A000699 := proc(n)
%p A000699     option remember;
%p A000699     if n <= 1 then
%p A000699         1;
%p A000699     else
%p A000699         add((2*i-1)*procname(i)*procname(n-i),i=1..n-1) ;
%p A000699     end if;
%p A000699 end proc:
%p A000699 seq(A000699(n),n=0..30) ; # _R. J. Mathar_, Jun 12 2018
%t A000699 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 A000699 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 A000699 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 A000699 (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 A000699 (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 A000699 (PARI)
%o A000699 seq(N) = {
%o A000699   my(a = vector(N)); a[1] = 1;
%o A000699   for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
%o A000699 };
%o A000699 seq(22)  \\ _Gheorghe Coserea_, Jan 22 2017
%o A000699 (PARI) seq(n)={my(g=serlaplace(1 / sqrt(1 - 2*x + O(x*x^n)))); Vec(sqrt((x/serreverse( x*g^2 ))))} \\ _Andrew Howroyd_, Nov 21 2024
%o A000699 (Python)
%o A000699 def A000699_list(n):
%o A000699     list = [1, 1] + [0] * (n - 1)
%o A000699     for i in range(2, n + 1):
%o A000699         list[i] = (i - 1) * sum(list[j] * list[i - j] for j in range(1, i))
%o A000699     return list
%o A000699 print(A000699_list(22)) # _M. Eren Kesim_, Jun 23 2021
%Y A000699 Sequences mentioned in the _Noam Zeilberger_ 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
%Y A000699 Cf. A004300, A051862, A212273. Column sums of A232223. First column of A322402.
%Y A000699 Cf. A007297, A016098, A099947, A136653, A268815, A306438, A324166, A324172, A324173, A324327.
%K A000699 nonn,easy,nice
%O A000699 0,4
%A A000699 _N. J. A. Sloane_
%E A000699 More terms from _David Broadhurst_, Dec 14 1999
%E A000699 Inserted "chord" in definition. - _N. J. A. Sloane_, Jan 19 2017
%E A000699 Added a(0)=1. - _N. J. A. Sloane_, Nov 05 2020
%E A000699 Modified formulas slightly to include a(0) = 1. - _Paul D. Hanna_, Nov 06 2020