A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

1, 0, 1, 4, 23, 157, 1182

Offset: 0

Author

Gus Wiseman, Jun 30 2019

Keywords

• nonn
• more

Comments

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

Links

• Gus Wiseman, The a(4) = 23 non-nesting connected simple graphs.
• Gus Wiseman, The a(5) = 157 non-nesting connected simple graphs.

Crossrefs

The inverse binomial transform is the non-covering case A326351.

Connected simple graphs are A001349.

Connected simple graphs with no crossing or nesting edges are A326294.

Simple graphs without crossing or nesting edges are A326244.

Cf. A006125, A054726, A117662, A136653.

Cf. A324169, A326210, A326293, A326329, 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