|
%I #10 Jun 28 2019 08:29:34
%S 1,1,2,8,36,160,704,3088,13536,59328,260032,1139712
%N Number of labeled n-vertex simple graphs without 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.
%H Gus Wiseman, <a href="/A326244/a326244.png">The a(4) = 36 non-crossing, non-nesting simple labeled graphs</a>.
%F A006125(n) = a(n) + A326279(n).
%F Conjectures from _Colin Barker_, Jun 28 2019: (Start)
%F G.f.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).
%F a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.
%F (End)
%t croXQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y];
%t nestQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<t<y||z<x<y<t];
%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!croXQ[#]&&!nestQ[#]&]],{n,0,5}]
%Y The case for set partitions is A001519.
%Y Simple graphs with crossing or nesting edges are A326279.
%Y Cf. A000088, A000108, A006125, A016098, A054726, A095661, A117662.
%Y Cf. A326209, A326210, A326250, A326255, A326256.
%K nonn,more
%O 0,3
%A _Gus Wiseman_, Jun 20 2019
|
