A327037 Number of pairwise intersecting set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

1, 1, 3, 21, 913, 1183295

Offset

0,3

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, covering set-systems that are cointersecting, meaning their dual is pairwise intersecting.

Links

Table of n, a(n) for n=0..5.

Formula

Inverse binomial transform of A327038.

Example

The a(0) = 1 through a(3) = 21 set-systems:
  {}  {{1}}  {{1,2}}      {{1,2,3}}
             {{1},{1,2}}  {{1},{1,2,3}}
             {{2},{1,2}}  {{2},{1,2,3}}
                          {{3},{1,2,3}}
                          {{1,2},{1,2,3}}
                          {{1,3},{1,2,3}}
                          {{2,3},{1,2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,2,3}}
                          {{1,2},{1,3},{2,3}}
                          {{2},{1,2},{1,2,3}}
                          {{2},{2,3},{1,2,3}}
                          {{3},{1,3},{1,2,3}}
                          {{3},{2,3},{1,2,3}}
                          {{1,2},{1,3},{1,2,3}}
                          {{1,2},{2,3},{1,2,3}}
                          {{1,3},{2,3},{1,2,3}}
                          {{1},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}
                          {{1,2},{1,3},{2,3},{1,2,3}}

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]=={}&], Union@@#==Range[n]&&stableQ[dual[#], Intersection[#1, #2]=={}&]&]], {n, 0, 4}]

Crossrefs

Intersecting covering set-systems are A305843.

The unlabeled multiset partition version is A319765.

The case where the dual is strict is A319774.

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

The non-covering version is A327038.

Cointersectng covering set-systems are A327040.

Cf. A003465, A319767, A326853, A326854, A326910.

Sequence in context: A127104 A176430 A340505 * A144621 A288567 A288568

Adjacent sequences: A327034 A327035 A327036 * A327038 A327039 A327040

Keyword

nonn,more

Author

Gus Wiseman, Aug 17 2019

Status

approved