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!)
A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices. 10
1, 0, 1, 14, 486, 71428 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

A connected vertex set in a clutter is any union of a connected subset of the edges.

LINKS

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

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

EXAMPLE

There are four connected vertex sets of {{1,2},{1,3},{2,3}}, namely {1,2,3}, {1,2}, {1,3}, {2,3}; there are three connected vertex sets of {{1,2},{1,3}}, {{1,2},{2,3}}, and {{1,3},{2,3}} each; and there is one connected vertex set of {{1,2,3}}. So we have a total of a(3) = 4 + 3 * 3 + 1 = 14 connected vertex sets.

MATHEMATICA

nn=5;

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], multijoin@@s[[c[[1]]]]]]]]];

clutQ[eds_]:=And[UnsameQ@@eds, !Apply[Or, Outer[#1=!=#2&&Complement[#1, #2]=={}&, eds, eds, 1], {0, 1}], Length[csm[eds]]==1];

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

swell[c_]:=Union@@FixedPointList[Union[ReplaceList[#1, {___, a:{___, x_, ___}, ___, b:{___, x_, ___}, ___}:>Union[a, b]]]&, c]

Table[Sum[Length[swell[c]], {c, Select[stableSets[Select[Subsets[Range[n]], Length[#]>1&], Complement[#1, #2]=={}&], And[Union@@#==Range[n], clutQ[#]]&]}], {n, nn}]

CROSSREFS

Cf. A001187, A006126, A030019, A048143, A134954, A275307, A286520, A293510, A304717, A317631, A317632, A317634.

Sequence in context: A331612 A275092 A275348 * A128051 A217337 A251867

Adjacent sequences:  A317632 A317633 A317634 * A317636 A317637 A317638

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Aug 02 2018

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 August 14 10:47 EDT 2020. Contains 336480 sequences. (Running on oeis4.)