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,4

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

Table of n, a(n) for n=0..11.

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.

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&!MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y||x<z<t<y||z<x<y<t]&]], {n, 0, 5}]

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.

Sequence in context: A273904 A027125 A027127 * A073717 A149427 A290907

Adjacent sequences: A326326 A326327 A326328 * A326330 A326331 A326332

Keyword

nonn,more

Author

Gus Wiseman, Jun 27 2019

Status

approved