|
| |
|
|
A326366
|
|
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
|
| |
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The a(0) = 1 through a(4) = 28 intersecting antichains with empty intersection:
{} {} {} {} {}
{{12}{13}{23}} {{12}{13}{23}}
{{12}{14}{24}}
{{13}{14}{34}}
{{23}{24}{34}}
{{12}{13}{234}}
{{12}{14}{234}}
{{12}{23}{134}}
{{12}{24}{134}}
{{13}{14}{234}}
{{13}{23}{124}}
{{13}{34}{124}}
{{14}{24}{123}}
{{14}{34}{123}}
{{23}{24}{134}}
{{23}{34}{124}}
{{24}{34}{123}}
{{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}}
|
|
|
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]]]];
Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&], #=={}||Intersection@@#=={}&]], {n, 0, 4}]
|
|
|
CROSSREFS
|
The case with empty edges allowed is A326375.
Intersecting antichains of nonempty sets are A001206.
Intersecting set systems with empty intersection are A326373.
Antichains of nonempty sets with empty intersection are A006126 or A307249.
The inverse binomial transform is the covering case A326365.
Cf. A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326361, A326362, A326363, A326364.
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
