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

%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