

A326339


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


6




OFFSET

0,4


COMMENTS

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.
Appears to be essentially the same as A003946.


LINKS



EXAMPLE

The a(2) = 1 through a(4) = 36 edgesets:
{12} {12,13} {12,13,14}
{12,23} {12,13,34}
{13,23} {12,14,34}
{12,13,23} {12,23,24}
{12,23,34}
{12,24,34}
{13,23,34}
{14,24,34}
{12,13,14,34}
{12,13,23,34}
{12,14,24,34}
{12,23,24,34}


MATHEMATICA

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[csm[#]]<=1&&!MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<tz<x<t<yx<z<t<yz<x<y<t]&]], {n, 0, 5}]


CROSSREFS

Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
The case with only crossing edges forbidden is A007297.
Graphs without crossing or nesting edges are A326244.


KEYWORD

nonn,more


AUTHOR



STATUS

approved



