login
Number of labeled n-vertex simple graphs containing either a crossing or a nesting pair of edges.
6

%I #4 Jun 25 2019 10:10:36

%S 0,0,0,0,28,864,32064,2094064

%N Number of labeled n-vertex simple graphs containing either a crossing or a nesting pair of 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.

%F A006125(n) = a(n) + A326244(n).

%e The a(4) = 28 edge-sets:

%e {13,24} {12,13,24} {12,13,14,23} {12,13,14,23,24} {12,13,14,23,24,34}

%e {14,23} {12,14,23} {12,13,14,24} {12,13,14,23,34}

%e {13,14,23} {12,13,23,24} {12,13,14,24,34}

%e {13,14,24} {12,13,24,34} {12,13,23,24,34}

%e {13,23,24} {12,14,23,24} {12,14,23,24,34}

%e {13,24,34} {12,14,23,34} {13,14,23,24,34}

%e {14,23,24} {13,14,23,24}

%e {14,23,34} {13,14,23,34}

%e {13,14,24,34}

%e {13,23,24,34}

%e {14,23,24,34}

%t croXQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y];

%t nesXQ[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[#]||nesXQ[#]&]],{n,0,5}]

%Y Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.

%Y Cf. A000108, A001519, A006125, A016098, A054726, A095661, A324170.

%Y Cf. A326209, A326211, A326248, A326250, A326256.

%K nonn,more

%O 0,5

%A _Gus Wiseman_, Jun 23 2019