A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

1, 0, 1, 0, 1, 11, 95, 797

Offset

0,6

Comments

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. 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.

Links

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

Gus Wiseman, The a(6) = 95 non-nesting, topologically connected, covering simple graphs.

Example

The a(5) = 11 edge-sets:
  {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}

Mathematica

croXQ[eds_]:=MatchQ[eds, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y];
nesXQ[eds_]:=MatchQ[eds, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];
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]&&!nesXQ[#]&&Length[csm[Union[Subsets[#, {1}], Select[Subsets[#, {2}], croXQ]]]]<=1&]], {n, 0, 5}]

Crossrefs

The binomial transform is the non-covering case A326293.

Topologically connected, covering simple graphs are A324327.

Non-crossing, covering simple graphs are A324169.

Cf. A000108, A000699, A006125, A054726, A099947, A117662.

Cf. A324323, A324328, A326329, A326330, A326339, A326341.

Sequence in context: A298925 A016203 A241606 * A318599 A347479 A051446

Adjacent sequences: A326346 A326347 A326348 * A326350 A326351 A326352

Keyword

nonn,more

Author

Gus Wiseman, Jun 30 2019

Status

approved