cp's OEIS Frontend

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

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