A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

1, 0, 1, 4, 13, 44, 149, 504, 1705, 5768, 19513, 66012

Offset: 0

Author

Gus Wiseman, Jun 27 2019

Keywords

• nonn
• more

Comments

Covering means there are no isolated vertices. 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.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Links

• Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
• Gus Wiseman, The a(5) = 44 covering simple graphs with no crossing or nesting edges.

Crossrefs

The case for set partitions is A001519.

Covering simple graphs are A006129.

The case with just nesting or just crossing edges forbidden is A324169.

The binomial transform is the non-covering case A326244.

Cf. A000108, A006125, A007297, A054726, A099947, A324327, A326279, A326293.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x