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

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

Offset

0,6

Comments

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.

Links

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

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

Mathematica

nesXQ[stn_]:=MatchQ[stn, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];
nestcmpts[stn_]:=csm[Union[List/@stn, Select[Subsets[stn, {2}], nesXQ]]];
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[nestcmpts[#]]<=1&]], {n, 0, 5}]

Crossrefs

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.

Sequence in context: A209096 A159645 A297805 * A210029 A292966 A109773

Adjacent sequences: A326328 A326329 A326330 * A326332 A326333 A326334

Keyword

nonn,more

Author

Gus Wiseman, Jun 27 2019

Status

approved