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

1, 0, 1, 4, 12, 36, 108, 324

Offset: 0

Author

Gus Wiseman, Jun 29 2019

Keywords

• nonn
• more

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.

Examples

			The a(2) = 1 through a(4) = 36 edge-sets:
  {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}
		

Links

• Gus Wiseman, The a(5) = 36 connected graphs with no crossing or nesting edges.
• Gus Wiseman, The a(6) = 108 connected graphs with no crossing or nesting edges.

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.

Cf. A006125, A054726, A117662, A136653.

Cf. A324169, A326210, A326293, A326340.

Programs

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