login
Number of ways to choose a stable partition of an antichain of sets spanning n vertices.
2

%I #7 Nov 26 2018 17:04:13

%S 1,1,3,25,773,160105

%N Number of ways to choose a stable partition of an antichain of sets spanning n vertices.

%C A stable partition of a hypergraph or set system is a set partition of the vertices where no non-singleton edge has all its vertices in the same block.

%e The a(3) = 25 stable partitions of antichains on 3 vertices. The antichain is on top, and below is a list of all its stable partitions.

%e {1}{2}{3} {1,2,3} {1}{2,3} {1,3}{2} {1,2}{3}

%e -------- -------- -------- -------- --------

%e {{1,2,3}} {{1},{2,3}} {{1,2},{3}} {{1},{2,3}} {{1},{2,3}}

%e {{1},{2,3}} {{1,2},{3}} {{1,3},{2}} {{1,2},{3}} {{1,3},{2}}

%e {{1,2},{3}} {{1,3},{2}} {{1},{2},{3}} {{1},{2},{3}} {{1},{2},{3}}

%e {{1,3},{2}} {{1},{2},{3}}

%e {{1},{2},{3}}

%e .

%e {1,3}{2,3} {1,2}{2,3} {1,2}{1,3} {1,2}{1,3}{2,3}

%e -------- -------- -------- --------

%e {{1,2},{3}} {{1,3},{2}} {{1},{2,3}} {{1},{2},{3}}

%e {{1},{2},{3}} {{1},{2},{3}} {{1},{2},{3}}

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%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 Table[Sum[Length[stableSets[Complement[Subsets[Range[n]],Union@@Subsets/@stn],SubsetQ]],{stn,sps[Range[n]]}],{n,5}]

%Y Cf. A000110, A000569, A006125, A006126, A229048, A240936, A277203, A321979, A322064, A322065.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Nov 25 2018