A326373 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) on n vertices.

1, 1, 1, 3, 435, 989555, 887050136795, 291072121058024908202443, 14704019422368226413236661148207899662350666147, 12553242487939461785560846872353486129110194529637343578112251094358919036718815137721635299

Offset: 0

Author

Gus Wiseman, Jul 01 2019

Keywords

• nonn

Comments

A set system (set of sets) is intersecting if no two edges are disjoint.

Examples

			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}}
		

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.

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

Formula

a(n) = A051185(n) - 1 - Sum_{k=1..n-1} binomial(n,k)*A000371(k). - Andrew Howroyd, Aug 12 2019

Extensions

a(6)-a(9) from Andrew Howroyd, Aug 12 2019