|
%I #5 Jun 30 2019 06:50:52
%S 1,0,1,0,1,11,95,797
%N Number of non-nesting, topologically connected simple graphs covering {1..n}.
%C Covering means there are no isolated vertices. 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. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.
%H Gus Wiseman, <a href="/A326349/a326349.png">The a(6) = 95 non-nesting, topologically connected, covering simple graphs</a>.
%e The a(5) = 11 edge-sets:
%e {13,14,25}
%e {13,24,25}
%e {13,24,35}
%e {14,24,35}
%e {14,25,35}
%e {13,14,24,25}
%e {13,14,24,35}
%e {13,14,25,35}
%e {13,24,25,35}
%e {14,24,25,35}
%e {13,14,24,25,35}
%t croXQ[eds_]:=MatchQ[eds,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y];
%t nesXQ[eds_]:=MatchQ[eds,{___,{x_,y_},___,{z_,t_},___}/;x<z<t<y||z<x<y<t];
%t 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 Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!nesXQ[#]&&Length[csm[Union[Subsets[#,{1}],Select[Subsets[#,{2}],croXQ]]]]<=1&]],{n,0,5}]
%Y The binomial transform is the non-covering case A326293.
%Y Topologically connected, covering simple graphs are A324327.
%Y Non-crossing, covering simple graphs are A324169.
%Y Cf. A000108, A000699, A006125, A054726, A099947, A117662.
%Y Cf. A324323, A324328, A326329, A326330, A326339, A326341.
%K nonn,more
%O 0,6
%A _Gus Wiseman_, Jun 30 2019
|
