A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

1, 0, 1, 4, 23, 157, 1182

Offset

0,4

Comments

Two edges {a,b}, {c,d} are nesting if a < c < d < b or c < a < b < d.

Links

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

Gus Wiseman, The a(4) = 23 non-nesting connected simple graphs.

Gus Wiseman, The a(5) = 157 non-nesting connected simple graphs.

Mathematica

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t]&]], {n, 0, 5}]

Crossrefs

The inverse binomial transform is the non-covering case A326351.

Connected simple graphs are A001349.

Connected simple graphs with no crossing or nesting edges are A326294.

Simple graphs without crossing or nesting edges are A326244.

Cf. A006125, A054726, A117662, A136653.

Cf. A324169, A326210, A326293, A326329, A326340.

Sequence in context: A366070 A007297 A263843 * A198916 A182969 A263186

Adjacent sequences: A326347 A326348 A326349 * A326351 A326352 A326353

Keyword

nonn,more

Author

Gus Wiseman, Jun 30 2019

Status

approved