A327038 Number of pairwise intersecting set-systems covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

1, 2, 6, 34, 1020, 1188106, 909149847892, 291200434288840793135801

Offset: 0

Author

Gus Wiseman, Aug 17 2019

Keywords

• nonn
• more

Comments

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence counts pairwise intersecting set-systems that are cointersecting, meaning their dual is pairwise intersecting.

Examples

			The a(0) = 1 through a(2) = 6 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{1,2}}
             {{2},{1,2}}
The a(3) = 34 set-systems:
  {}  {{1}}    {{1}{12}}    {{1}{12}{123}}   {{1}{12}{13}{123}}
      {{2}}    {{1}{13}}    {{1}{13}{123}}   {{2}{12}{23}{123}}
      {{3}}    {{2}{12}}    {{12}{13}{23}}   {{3}{13}{23}{123}}
      {{12}}   {{2}{23}}    {{2}{12}{123}}   {{12}{13}{23}{123}}
      {{13}}   {{3}{13}}    {{2}{23}{123}}
      {{23}}   {{3}{23}}    {{3}{13}{123}}
      {{123}}  {{1}{123}}   {{3}{23}{123}}
               {{2}{123}}   {{12}{13}{123}}
               {{3}{123}}   {{12}{23}{123}}
               {{12}{123}}  {{13}{23}{123}}
               {{13}{123}}
               {{23}{123}}
		

Crossrefs

Intersecting set-systems are A051185.

The unlabeled multiset partition version is A319765.

The BII-numbers of these set-systems are A326912.

The covering case is A327037.

Cointersecting set-systems are A327039.

The case where the dual is strict is A327040.

Cf. A058891, A319767, A319774, A326854, A327052.

Programs

Mathematica

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
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]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],Intersection[#1,#2]=={}&],stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,4}]

Formula

Binomial transform of A327037.

Extensions

a(6)-a(7) from Christian Sievers, Aug 18 2024