A326363 Number of maximal intersecting antichains of subsets of {1..n}.

1, 2, 4, 6, 21, 169, 11749, 12160648

Offset: 0

Author

Gus Wiseman, Jul 01 2019

Keywords

• nonn
• more

Comments

A set system (set of sets) is an antichain if no element is a subset of any other, and is intersecting if no two element are disjoint.

Examples

			The a(1) = 1 through a(4) = 21 maximal intersecting antichains:
  {}   {}    {}            {}
  {1}  {1}   {1}           {1}
       {2}   {2}           {2}
       {12}  {3}           {3}
             {123}         {4}
             {12}{13}{23}  {1234}
                           {12}{13}{23}
                           {12}{14}{24}
                           {13}{14}{34}
                           {23}{24}{34}
                           {12}{134}{234}
                           {13}{124}{234}
                           {14}{123}{234}
                           {23}{124}{134}
                           {24}{123}{134}
                           {34}{123}{124}
                           {12}{13}{14}{234}
                           {12}{23}{24}{134}
                           {13}{23}{34}{124}
                           {14}{24}{34}{123}
                           {123}{124}{134}{234}
		

Crossrefs

The case with nonempty, non-singleton edges is A326362.

Antichains of nonempty, non-singleton sets are A307249.

Minimal covering antichains are A046165.

Maximal intersecting antichains are A007363.

Maximal antichains of nonempty sets are A326359.

Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326361.

Programs

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],{0,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]]],{n,0,5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
Length[sets] (* Elijah Beregovsky, May 06 2020 *)

Formula

For n > 1, a(n) = A007363(n + 1) + 1 = A326362(n) + n + 1.

Extensions

a(7) from Elijah Beregovsky, May 06 2020