|
%I #8 Jun 29 2019 23:01:57
%S 1,1,2,8,35,147,600,2418
%N Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.
%C 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.
%H Eric Marberg, <a href="http://arxiv.org/abs/1203.5738">Crossings and nestings in colored set partitions</a>, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
%F Conjecture: a(n) = A052161(n - 2) + 1.
%e The a(4) = 35 edge-sets:
%e {} {12} {12,13} {12,13,14} {12,13,14,34}
%e {13} {12,14} {12,13,23} {12,13,23,34}
%e {14} {12,23} {12,13,34} {12,14,24,34}
%e {23} {12,24} {12,14,24} {12,23,24,34}
%e {24} {13,14} {12,14,34}
%e {34} {13,23} {12,23,24}
%e {13,34} {12,23,34}
%e {14,24} {12,24,34}
%e {14,34} {13,14,34}
%e {23,24} {13,23,34}
%e {23,34} {14,24,34}
%e {24,34} {23,24,34}
%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}]],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 The inverse binomial transform is the covering case A326339.
%Y Covering graphs with no crossing or nesting edges are A326329.
%Y Connected simple graphs are A001349.
%Y Graphs without crossing or nesting edges are A326244.
%Y Cf. A006125, A054726, A117662, A136653.
%Y Cf. A324169, A326210, A326293, A326340.
%K nonn,more
%O 0,3
%A _Gus Wiseman_, Jun 29 2019
|
