|
%I #5 Aug 03 2018 08:16:37
%S 1,0,1,14,486,71428
%N Number of connected vertex sets of clutters (connected antichains) spanning n vertices.
%C A connected vertex set in a clutter is any union of a connected subset of the edges.
%H Gus Wiseman, <a href="http://www.mathematica-journal.com/2017/12/every-clutter-is-a-tree-of-blobs/">Every Clutter Is a Tree of Blobs</a>, The Mathematica Journal, Vol. 19, 2017.
%e 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.
%t nn=5;
%t 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]]]]]]]]];
%t clutQ[eds_]:=And[UnsameQ@@eds,!Apply[Or,Outer[#1=!=#2&&Complement[#1,#2]=={}&,eds,eds,1],{0,1}],Length[csm[eds]]==1];
%t 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]]]];
%t swell[c_]:=Union@@FixedPointList[Union[ReplaceList[#1,{___,a:{___,x_,___},___,b:{___,x_,___},___}:>Union[a,b]]]&,c]
%t Table[Sum[Length[swell[c]],{c,Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Complement[#1,#2]=={}&],And[Union@@#==Range[n],clutQ[#]]&]}],{n,nn}]
%Y Cf. A001187, A006126, A030019, A048143, A134954, A275307, A286520, A293510, A304717, A317631, A317632, A317634.
%K nonn,more
%O 0,4
%A _Gus Wiseman_, Aug 02 2018
|
