cp's OEIS Frontend

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

%I A326339 #9 Jun 30 2019 06:50:29
%S A326339 1,0,1,4,12,36,108,324
%N A326339 Number of connected simple graphs with vertices {1..n} and no crossing or nesting edges.
%C A326339 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.
%C A326339 Appears to be essentially the same as A003946.
%H A326339 Gus Wiseman, <a href="/A326339/a326339.png">The a(5) = 36 connected graphs with no crossing or nesting edges</a>.
%H A326339 Gus Wiseman, <a href="/A326339/a326339_1.png">The a(6) = 108 connected graphs with no crossing or nesting edges</a>.
%e A326339 The a(2) = 1 through a(4) = 36 edge-sets:
%e A326339   {12}  {12,13}     {12,13,14}
%e A326339         {12,23}     {12,13,34}
%e A326339         {13,23}     {12,14,34}
%e A326339         {12,13,23}  {12,23,24}
%e A326339                     {12,23,34}
%e A326339                     {12,24,34}
%e A326339                     {13,23,34}
%e A326339                     {14,24,34}
%e A326339                     {12,13,14,34}
%e A326339                     {12,13,23,34}
%e A326339                     {12,14,24,34}
%e A326339                     {12,23,24,34}
%t A326339 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]]]]]]]]];
%t A326339 Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y||x<z<t<y||z<x<y<t]&]],{n,0,5}]
%Y A326339 Covering graphs with no crossing or nesting edges are A326329.
%Y A326339 Connected simple graphs are A001349.
%Y A326339 The case with only crossing edges forbidden is A007297.
%Y A326339 Graphs without crossing or nesting edges are A326244.
%Y A326339 Cf. A006125, A054726, A117662, A136653.
%Y A326339 Cf. A324169, A326210, A326293, A326340.
%K A326339 nonn,more
%O A326339 0,4
%A A326339 _Gus Wiseman_, Jun 29 2019