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

Offset: 0

Author

Gus Wiseman, Jun 20 2019

Keywords

• nonn
• more

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.
• Gus Wiseman, The a(4) = 36 non-crossing, non-nesting simple labeled graphs.

Crossrefs

The case for set partitions is A001519.

Simple graphs with crossing or nesting edges are A326279.

Cf. A000088, A000108, A006125, A016098, A054726, A095661, A117662.

Cf. A326209, A326210, A326250, A326255, A326256.

Programs

Mathematica

croXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x
				

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)