A324327 -id:A324327 - cp's OEIS frontend

A000699 Number of irreducible chord diagrams with 2n nodes.

1, 1, 1, 4, 27, 248, 2830, 38232, 593859, 10401712, 202601898, 4342263000, 101551822350, 2573779506192, 70282204726396, 2057490936366320, 64291032462761955, 2136017303903513184, 75197869250518812754, 2796475872605709079512, 109549714522464120960474, 4509302910783496963256400, 194584224274515194731540740

Offset: 0

N. J. A. Sloane

Perturbation expansion in quantum field theory: spinor case in 4 spacetime dimensions.
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
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
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
From Julien Courtiel, Oct 09 2024: (Start)
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.
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.
(End)

			a(31)=627625976637472254550352492162870816129760 was computed using Kreimer's Hopf algebra of rooted trees. It subsumes 2.6*10^21 terms in quantum field theory.
G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 27*x^4 + 248*x^5 + 2830*x^6 +...
where d/dx (A(x) - 1)^2/x = 1 + 4*x + 27*x^2 + 248*x^3 + 2830*x^4 +...

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

Alois P. Heinz, Table of n, a(n) for n = 0..404 (terms up to n=100 from T. D. Noe)
Serban T. Belinschi, Marek Bozejko, Franz Lehner, and Roland Speicher, The normal distribution is "boxplus"-infinitely divisible, arXiv:0910.4263 [math.OA], 2009-2010.
Daniel J. Bernstein, S. Engels, T. Lange, R. Niederhagen, et al., Faster elliptic-curve discrete logarithms on FPGAs, Preprint, 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, El. J. Combin. 25 (2018) P4.1, Sect 7.1.
Michael Borinsky, Gerald V. Dunne, and Karen Yeats, Tree-tubings and the combinatorics of resurgent Dyson-Schwinger equations, arXiv:2408.15883 [math-ph], 2024. See p. 9.
David J. Broadhurst and Dirk Kreimer, Combinatoric explosion of renormalization ..., arXiv:hep-th/9912093, 1999, 2000.
David J. Broadhurst and Dirk Kreimer, Combinatoric explosion of renormalization tamed by Hopf algebra: 30-loop Pad-Borel resummation, Phys. Lett. B 475 (2000), 63-70.
Christian Brouder, On the trees of quantum fields, arXiv:hep-th/9906111, 1999, p. 6.
Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts).
Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, May 23, 2011.
Jonathan Burns and Tilahun Muche, Counting Irreducible Double Occurrence Words, arXiv preprint arXiv:1105.2926 [math.CO], 2011.
Julien Courtiel, Karen Yeats, and Noam Zeilberger, Connected chord diagrams and bridgeless maps, arXiv:1611.04611 [math.CO], 2016.
Serge Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)
Philippe Flajolet and Marc Noy, Analytic Combinatorics of Chord Diagrams, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, pp. 191-201.
Zhen Huang, Denis Golež, Hugo U. R. Strand, and Jason Kaye, Automated evaluation of imaginary time strong coupling diagrams by sum-of-exponentials hybridization fitting, arXiv:2503.19727 [cond-mat.str-el], 2025. See p. 21.
Martin Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.
Martin Klazar, Counting even and odd partitions, Amer. Math. Monthly, 110 (No. 6, 2003), 527-532.
Florian Kogelbauer and Ilya Karlin, On the Relation of Exact Hydrodynamics to the Chapman-Enskog Series, arXiv:2506.17441 [math-ph], 2025. See pp. 4-5.
Ali Assem Mahmoud, On the Asymptotics of Connected Chord Diagrams, University of Waterloo (Ontario, Canada 2019).
Ali Assem Mahmoud, An Asymptotic Expansion for the Number of 2-Connected Chord Diagrams, arXiv:2009.12688 [math.CO], 2020.
Ali Assem Mahmoud, Chord Diagrams and the Asymptotic Analysis of QED-type Theories, arXiv:2011.04291 [hep-th], 2020.
Ali Assem Mahmoud, An asymptotic expansion for the number of two-connected chord diagrams, J. Math. Phys. (2023) Vol. 64, 122301. See Example 2.1.
Ali Assem Mahmoud and Karen Yeats, Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions, arXiv:2010.06550 [math.CO], 2020.
Nicolas Marie and Karen Yeats, A chord diagram expansion coming from some Dyson-Schwinger equations, arXiv:1210.5457 [math.CO], 2012, Section 4.1.
Albert Nijenhuis and Herbert S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074).
Vincent Pilaud and Juanjo Rué, Analytic combinatorics of chord and hyperchord diagrams with k crossings, arXiv preprint arXiv:1307.6440 [math.CO], 2013.
J. Riordan, Letter, Jul 06 1978
Einar A. Rødland, Pseudoknots in RNA Secondary Structures: Representation, Enumeration, and Prevalence, J. Comput. Biology, Vol 13, No 6 (2006), 1197-1213. (see equation 10)
R. R. Stein, On a class of linked diagrams, I. Enumeration, J. Combin. Theory, A 24 (1978), 357-366.
R. R. Stein and C. J. Everett, On a class of linked diagrams, II. Asymptotics, Discrete Math., 21 (1978), 309-318.
Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25.
Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25. [Annotated, corrected, scanned copy]
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259 (nonseparable integer systems on n pairs). (Give an incorrect a(6)=2720.)
Gus Wiseman, The a(4) = 27 connected chord diagrams.
Gus Wiseman, The a(5) = 248 connected chord diagrams.
Gus Wiseman, Constructive Mathematica program for A000699.
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv:1803.10080 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Rutgers Experimental Math Seminar, Sep 13 2018. Part 2 is vimeo.com/289910554.

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
Cf. A004300, A051862, A212273. Column sums of A232223. First column of A322402.
Cf. A007297, A016098, A099947, A136653, A268815, A306438, A324166, A324172, A324173, A324327.

A000699 := proc(n)
    option remember;
    if n <= 1 then
        1;
    else
        add((2*i-1)*procname(i)*procname(n-i),i=1..n-1) ;
    end if;
end proc:
seq(A000699(n),n=0..30) ; # R. J. Mathar, Jun 12 2018

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 *)
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 *)
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 *)

{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]

{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] */

seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(22)  \\ Gheorghe Coserea, Jan 22 2017

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

def A000699_list(n):
    list = [1, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        list[i] = (i - 1) * sum(list[j] * list[i - j] for j in range(1, i))
    return list
print(A000699_list(22)) # M. Eren Kesim, Jun 23 2021

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]
A212273(n) = n * a(n). - Michael Somos, May 12 2012
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]
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
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
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

More terms from David Broadhurst, Dec 14 1999
Inserted "chord" in definition. - N. J. A. Sloane, Jan 19 2017
Added a(0)=1. - N. J. A. Sloane, Nov 05 2020
Modified formulas slightly to include a(0) = 1. - Paul D. Hanna, Nov 06 2020

A136653 G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 4, 39, 748, 27162, 1880872, 252273611, 66358216668, 34506398937158, 35644762692112792, 73356520492898454022, 301274559225693420690360, 2471654510727312089903896948, 40527708183358718551543295827536, 1328579216048284168977214446788083699

Offset: 0

Paul D. Hanna, Jan 15 2008

nonn

a(n) is the number of graphs on vertices 1,...,n such that, when these vertices are arranged counterclockwise around a circle and edges are drawn as straight line segments, the resulting diagram is connected. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

In this interpretation, both intersecting (set theoretically) and crossing (topologically) edges are considered connected. - Gus Wiseman, Feb 23 2019

			G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 39*x^4 + 748*x^5 + 27162*x^6 +...
Let F(x) = 1 + x + 2*x^2 + 8*x^3 + 64*x^4 + 1024*x^5 +...+ 2^(n*(n-1)/2)*x^n +..
then A(x) = F(x/A(x)), A(x*F(x)) = F(x).
Coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2),
as can be seen by the main diagonal in the array of
coefficients in the initial powers of A(x):
A^1: [(1), 1, 1, 4, 39, 748, 27162, 1880872, 252273611,...;
A^2: [1, (2), 3, 10, 87, 1582, 55914, 3817876, 508370795,...;
A^3: [1, 3, (6), 19, 147, 2517, 86398, 5813550, 768378627,...;
A^4: [1, 4, 10, (32), 223, 3572, 118778, 7870640, 1032387787,...;
A^5: [1, 5, 15, 50, (320), 4771, 153245, 9992130, 1300492845,...;
A^6: [1, 6, 21, 74, 444, (6144), 190023, 12181278, 1572792585,...;
A^7: [1, 7, 28, 105, 602, 7728, (229376), 14441659, 1849390375,...;
A^8: [1, 8, 36, 144, 802, 9568, 271616, (16777216), 2130394591,...;
A^9: [1, 9, 45, 192, 1053, 11718, 317112, 19192320, (2415919104),...;
dividing each diagonal term in row n by (n+1) gives 2^(n*(n-1)/2).
The diagonal above the main diagonal gives coefficients of l.g.f.:
log(F(x)) = x + 3*x^2/2 + 19*x^3/3 + 223*x^4/4 + 4771*x^5/5 +...

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 39 graphs connected by overlaps or crossings.

Cf. A136652 (log(A(x))), A136654.
Cf. A000699, A002662, A006125, A007297, A016098, A054726, A099947, A306438.
Cf. A324166, A324169, A324172, A324173, A324327, A324328.

max = 15; s = x*Sum[2^(k*(k-1)/2)*x^k, {k, 0, max}] + O[x]^(max+2); x/InverseSeries[s] + O[x]^(max+1) // CoefficientList[#, x]& (* Jean-François Alcover, Sep 03 2017 *)
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
bicmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],Intersection@@#!={}&],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[bicmpts[#]]<=1]&]],{n,0,5}] (* Gus Wiseman, Feb 23 2019 *)

a(n)=polcoeff(x/serreverse(x*sum(k=0,n,2^(k*(k-1)/2)*x^k +x*O(x^n))),n)

G.f.: A(x) = x/Series_Reversion( x*Sum_{k=0..n} 2^(k(k-1)/2)*x^k ).

Equals the free cumulant sequence corresponding to A006125. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

Name changed and part of prior name moved to formula section by Paul D. Hanna, Sep 19 2013

A326293 Number of non-nesting, topologically connected simple graphs with vertices {1..n}.

Original entry on oeis.org

1, 1, 2, 4, 8, 27, 192, 1750

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

Gus Wiseman, The a(5) = 27 non-nesting, topologically connected simple graphs.

The inverse binomial transform is the covering case A326349.
Topologically connected simple graphs are A324328.
Non-crossing simple graphs are A054726.
Topologically connected set partitions are A099947.
Cf. A000108, A000699, A006125, A007297, A117662, A136653.
Cf. A324173, A324323, A324327, A326244, A326330, A326341.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!nesXQ[#]&&Length[csm[Union[Subsets[#,{1}],Select[Subsets[#,{2}],croXQ]]]]<=1&]],{n,0,5}]

A324328 Number of topologically connected chord graphs on a subset of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 4, 8, 27, 354

Offset: 0

Gus Wiseman, Feb 22 2019

A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected, where two edges cross each other if they are of the form {{x,y},{z,t}} with x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(5) = 27 graphs:
  {}  {}  {}      {}      {}          {}
          {{12}}  {{12}}  {{12}}      {{12}}
                  {{13}}  {{13}}      {{13}}
                  {{23}}  {{14}}      {{14}}
                          {{23}}      {{15}}
                          {{24}}      {{23}}
                          {{34}}      {{24}}
                          {{13}{24}}  {{25}}
                                      {{34}}
                                      {{35}}
                                      {{45}}
                                      {{13}{24}}
                                      {{13}{25}}
                                      {{14}{25}}
                                      {{14}{35}}
                                      {{24}{35}}
                                      {{13}{14}{25}}
                                      {{13}{24}{25}}
                                      {{13}{24}{35}}
                                      {{14}{24}{35}}
                                      {{14}{25}{35}}
                                      {{13}{14}{24}{25}}
                                      {{13}{14}{24}{35}}
                                      {{13}{14}{25}{35}}
                                      {{13}{24}{25}{35}}
                                      {{14}{24}{25}{35}}
                                      {{13}{14}{24}{25}{35}}

Cf. A000108, A000699, A001764, A002061, A007297, A016098, A054726 (non-crossing chord graphs), A099947, A136653, A268814.

Cf. A324168, A324169, A324172, A324173, A324323, A324327 (covering case).

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[crosscmpts[#]]<=1&]],{n,0,5}]

Binomial transform of A324327.

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Original entry on oeis.org

1, 0, 1, 4, 13, 44, 149, 504, 1705, 5768, 19513, 66012

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(5) = 44 covering simple graphs with no crossing or nesting edges.

The case for set partitions is A001519.
Covering simple graphs are A006129.
The case with just nesting or just crossing edges forbidden is A324169.
The binomial transform is the non-covering case A326244.
Cf. A000108, A006125, A007297, A054726, A099947, A324327, A326279, A326293.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Original entry on oeis.org

1, 0, 1, 3, 29, 595, 23437

Offset: 0

Gus Wiseman, Jun 28 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. A graph has its weakly nesting edges connected if the graph whose vertices are the edges and whose edges are weakly nesting pairs of edges is connected.

Gus Wiseman, The a(4) = 29 covering simple graphs whose weakly nesting edges are connected.

The binomial transform is the non-covering case A326338.
The non-weak case is A326331.
Simple graphs whose nesting edges are connected are A326330.
Cf. A006125, A007297, A054726, A099947, A136653.
Cf. A324169, A324327, A326293, A326294, A326329, A326335, A326336.

wknXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;(x<=z&&y>=t)||(x>=z&&y<=t)];
wknestcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],wknXQ]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[wknestcmpts[#]]<=1&]],{n,0,5}]

A326331 Number of simple graphs covering the vertices {1..n} whose nesting edges are connected.

Original entry on oeis.org

1, 0, 1, 0, 1, 14, 539

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are nesting if a < c < d < b or c < a < b < d. A graph has its nesting edges connected if the graph whose vertices are the edges and whose edges are nesting pairs of edges is connected.

Gus Wiseman, The a(5) = 14 simple nesting-connected covering graphs.

The non-covering case is the binomial transform A326330.
Covering graphs whose crossing edges are connected are A324327.
Cf. A006125, A007297, A054726, A099947, A117662, A136653, A324328.
Cf. A326210, A326293, A326335, A326336, A326337, A326338, A326339.

nesXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[nestcmpts[#]]<=1&]],{n,0,5}]

A326340 Number of maximal simple graphs with vertices {1..n} and no crossing or nesting edges.

Original entry on oeis.org

1, 1, 1, 1, 4, 9, 19, 42

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Gus Wiseman, The a(6) = 19 maximal non-crossing non-nesting graphs.

Covering graphs with no crossing or nesting edges are A326329.
The case with only crossing edges forbidden is A000108 shifted right twice.
Simple graphs without crossing or nesting edges are A326244.
Connected graphs with no crossing or nesting edges are A326339.
Cf. A006125, A007297, A054726, A117662, A136653.
Cf. A324169, A324327, A324328, A326279, A326293.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Subsets[Range[n],{2}]],!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A322402 Triangle read by rows: The number of chord diagrams with n chords and k topologically connected components, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 4, 6, 5, 0, 27, 36, 28, 14, 0, 248, 310, 225, 120, 42, 0, 2830, 3396, 2332, 1210, 495, 132, 0, 38232, 44604, 29302, 14560, 6006, 2002, 429, 0, 593859, 678696, 430200, 204540, 81900, 28392, 8008, 1430, 0, 10401712, 11701926, 7204821, 3289296, 1263780, 431256, 129948, 31824, 4862

Offset: 0

R. J. Mathar, Dec 06 2018

If all subsets are allowed instead of just pairs (chords), we get A324173. The rightmost column is A000108 (see Riordan). - Gus Wiseman, Feb 27 2019

			From _Gus Wiseman_, Feb 27 2019: (Start)
Triangle begins:
  1
  0      1
  0      1      2
  0      4      6      5
  0     27     36     28     14
  0    248    310    225    120     42
  0   2830   3396   2332   1210    495    132
  0  38232  44604  29302  14560   6006   2002    429
  0 593859 678696 430200 204540  81900  28392   8008   1430
Row n = 3 counts the following chord diagrams (see link for pictures):
  {{1,3},{2,5},{4,6}}  {{1,2},{3,5},{4,6}}  {{1,2},{3,4},{5,6}}
  {{1,4},{2,5},{3,6}}  {{1,3},{2,4},{5,6}}  {{1,2},{3,6},{4,5}}
  {{1,4},{2,6},{3,5}}  {{1,3},{2,6},{4,5}}  {{1,4},{2,3},{5,6}}
  {{1,5},{2,4},{3,6}}  {{1,5},{2,3},{4,6}}  {{1,6},{2,3},{4,5}}
                       {{1,5},{2,6},{3,4}}  {{1,6},{2,5},{3,4}}
                       {{1,6},{2,4},{3,5}}
(End)

P. Flajolet and M. Noy, Analytic Combinatorics of Chord Diagrams, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, p 191-201, eq (2)
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
Gus Wiseman, Chords diagrams with 3 chords, organized by number of components.

Cf. A000699 (k = 1 column), A001147 (row sums), A000108 (diagonal), A002694 (subdiagonal k = n - 1).

Cf. A000096, A003436, A016098, A099947, A136653, A278990, A293157, A324173, A324323, A324327, A324328.

The g.f. satisfies g(z,w) = 1+w*A000699(w*g^2), where A000699(z) is the g.f. of A000699.

Offset changed to 0 by Gus Wiseman, Feb 27 2019

cp's OEIS Frontend

A000699 Number of irreducible chord diagrams with 2n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A136653 G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326293 Number of non-nesting, topologically connected simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A324328 Number of topologically connected chord graphs on a subset of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326331 Number of simple graphs covering the vertices {1..n} whose nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326340 Number of maximal simple graphs with vertices {1..n} and no crossing or nesting edges.