login
Number of intersecting antichains of nonempty subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).
5

%I #16 Aug 14 2019 18:22:54

%S 1,1,1,2,28,1960,1379273,229755337549,423295079757497714059

%N Number of intersecting antichains of nonempty subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).

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

%F a(n) = A326375(n) - 1.

%F a(n) = A001206(n+1) + A307249(n) - A014466(n). - _Andrew Howroyd_, Aug 14 2019

%e The a(0) = 1 through a(4) = 28 intersecting antichains with empty intersection:

%e {} {} {} {} {}

%e {{12}{13}{23}} {{12}{13}{23}}

%e {{12}{14}{24}}

%e {{13}{14}{34}}

%e {{23}{24}{34}}

%e {{12}{13}{234}}

%e {{12}{14}{234}}

%e {{12}{23}{134}}

%e {{12}{24}{134}}

%e {{13}{14}{234}}

%e {{13}{23}{124}}

%e {{13}{34}{124}}

%e {{14}{24}{123}}

%e {{14}{34}{123}}

%e {{23}{24}{134}}

%e {{23}{34}{124}}

%e {{24}{34}{123}}

%e {{12}{134}{234}}

%e {{13}{124}{234}}

%e {{14}{123}{234}}

%e {{23}{124}{134}}

%e {{24}{123}{134}}

%e {{34}{123}{124}}

%e {{12}{13}{14}{234}}

%e {{12}{23}{24}{134}}

%e {{13}{23}{34}{124}}

%e {{14}{24}{34}{123}}

%e {{123}{124}{134}{234}}

%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[Length[Select[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&],#=={}||Intersection@@#=={}&]],{n,0,4}]

%Y The case with empty edges allowed is A326375.

%Y Intersecting antichains of nonempty sets are A001206.

%Y Intersecting set systems with empty intersection are A326373.

%Y Antichains of nonempty sets with empty intersection are A006126 or A307249.

%Y The inverse binomial transform is the covering case A326365.

%Y Cf. A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326361, A326362, A326363, A326364.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Jul 01 2019

%E a(7)-a(8) from _Andrew Howroyd_, Aug 14 2019