|
| |
|
|
A326358
|
|
Number of maximal antichains of subsets of {1..n}.
|
|
10
|
| |
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
A set system (set of sets) is an antichain if no element is a subset of any other.
|
|
|
LINKS
|
Table of n, a(n) for n=0..7.
|
|
|
FORMULA
|
For n > 0, a(n) = A326359(n) + 1.
|
|
|
EXAMPLE
|
The a(0) = 1 through a(3) = 7 maximal antichains:
{} {} {} {}
{1} {12} {123}
{1}{2} {1}{23}
{2}{13}
{3}{12}
{1}{2}{3}
{12}{13}{23}
|
|
|
MATHEMATICA
|
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]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n]], SubsetQ]]], {n, 0, 5}]
(* alternatively *)
maxachP[n_]:=FindIndependentVertexSet[
Flatten[Map[Function[s, Map[# \[DirectedEdge] s &, Most[Subsets[s]]]],
Subsets[Range[n]]]], Infinity, All];
Table[Length[maxachP[n]], {n, 0, 6}] (* Mamuka Jibladze, Jan 25 2021 *)
|
|
|
PROG
|
(GAP) LoadPackage("grape");
maxachP:=function(n) local g, G;
g:=Graph(Group(()), Combinations([1..n]), function(x, g) return x; end,
function(x, y) return not IsSubset(x, y) and not IsSubset(y, x); end, true);
G:=AutGroupGraph(g);
return Sum(CompleteSubgraphs(NewGroupGraph(G, g), -1, 2),
function(c) return Length(Orbit(G, c, OnSets)); end);
end;
List([0..7], maxachP); # Mamuka Jibladze, Jan 26 2021
|
|
|
CROSSREFS
|
Antichains of sets are A000372.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305001, A305844, A326360, A326361, A326362, A326363.
Sequence in context: A072469 A004062 A037151 * A008840 A268477 A156313
Adjacent sequences: A326355 A326356 A326357 * A326359 A326360 A326361
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
Gus Wiseman, Jul 01 2019
|
|
|
EXTENSIONS
|
a(6)-a(7) from Mamuka Jibladze, Jan 26 2021
|
|
|
STATUS
|
approved
|
| |
|
|
