login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}. 2
1, 0, 1, 0, 1, 11, 95, 797 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

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. 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(6) = 95 non-nesting, topologically connected, covering simple graphs.

EXAMPLE

The a(5) = 11 edge-sets:

  {13,14,25}

  {13,24,25}

  {13,24,35}

  {14,24,35}

  {14,25,35}

  {13,14,24,25}

  {13,14,24,35}

  {13,14,25,35}

  {13,24,25,35}

  {14,24,25,35}

  {13,14,24,25,35}

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}]], Union@@#==Range[n]&&!nesXQ[#]&&Length[csm[Union[Subsets[#, {1}], Select[Subsets[#, {2}], croXQ]]]]<=1&]], {n, 0, 5}]

CROSSREFS

The binomial transform is the non-covering case A326293.

Topologically connected, covering simple graphs are A324327.

Non-crossing, covering simple graphs are A324169.

Cf. A000108, A000699, A006125, A054726, A099947, A117662.

Cf. A324323, A324328, A326329, A326330, A326339, A326341.

Sequence in context: A298925 A016203 A241606 * A318599 A051446 A271632

Adjacent sequences:  A326346 A326347 A326348 * A326350 A326351 A326352

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 30 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 16:29 EDT 2020. Contains 334748 sequences. (Running on oeis4.)