A326293 Number of non-nesting, topologically connected simple graphs with vertices {1..n}.

1, 1, 2, 4, 8, 27, 192, 1750

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. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

Links

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

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

Mathematica

croXQ[eds_]:=MatchQ[eds, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y];
nesXQ[eds_]:=MatchQ[eds, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];
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}]], !nesXQ[#]&&Length[csm[Union[Subsets[#, {1}], Select[Subsets[#, {2}], croXQ]]]]<=1&]], {n, 0, 5}]

Crossrefs

The inverse binomial transform is the covering case A326349.

Topologically connected simple graphs are A324328.

Non-crossing simple graphs are A054726.

Topologically connected set partitions are A099947.

Cf. A000108, A000699, A006125, A007297, A117662, A136653.

Cf. A324173, A324323, A324327, A326244, A326330, A326341.

Sequence in context: A037170 A212409 A006399 * A324328 A056800 A302915

Adjacent sequences: A326290 A326291 A326292 * A326294 A326295 A326296

Keyword

nonn,more

Author

Gus Wiseman, Jun 29 2019

Status

approved