A326279 - OEIS

A326279

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

0, 0, 0, 0, 28, 864, 32064, 2094064

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

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.

LINKS

FORMULA

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

EXAMPLE

The a(4) = 28 edge-sets:

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

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

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

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

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

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

{14,23,24} {13,14,23,24}

{14,23,34} {13,14,23,34}

{13,14,24,34}

{13,23,24,34}

{14,23,24,34}

MATHEMATICA

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

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

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], croXQ[#]||nesXQ[#]&]], {n, 0, 5}]

CROSSREFS

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

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 23 2019

STATUS

approved