|
|
A326373
|
|
Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) on n vertices.
|
|
3
|
|
|
1, 1, 1, 3, 435, 989555, 887050136795, 291072121058024908202443, 14704019422368226413236661148207899662350666147, 12553242487939461785560846872353486129110194529637343578112251094358919036718815137721635299
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A set system (set of sets) is intersecting if no two edges are disjoint.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(3) = 3 intersecting set systems with empty intersection:
{}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
|
|
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}], Intersection[#1, #2]=={}&], And[#=={}||Intersection@@#=={}]&]], {n, 0, 4}]
|
|
CROSSREFS
|
The inverse binomial transform is the covering case A326364.
Set systems with empty intersection are A318129.
Intersecting set systems are A051185.
Intersecting antichains with empty intersection are A326366.
Cf. A000371, A006126, A007363, A014466, A058891, A305844, A307249, A318128, A326361, A326362, A326363, A326365.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|