A326244 - OEIS

A326244

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

1, 1, 2, 8, 36, 160, 704, 3088, 13536, 59328, 260032, 1139712

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

OFFSET

0,3

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

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

FORMULA

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

Conjectures from Colin Barker, Jun 28 2019: (Start)

G.f.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).

a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.

(End)

MATHEMATICA

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

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

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

CROSSREFS

The case for set partitions is A001519.

Simple graphs with crossing or nesting edges are A326279.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 20 2019

STATUS

approved