A059052 -id:A059052 - cp's OEIS frontend

A326965 Number of set-systems on n vertices where every covered vertex is the unique common element of some subset of the edges.

1, 2, 5, 46, 19181, 2010327182, 9219217424630040409, 170141181796805106025395618012972506978, 57896044618658097536026644159052312978532934306727333157337631572314050272137

Offset: 0

Gus Wiseman, Aug 10 2019

nonn

A set-system is a finite set of finite nonempty sets. 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}}. An antichain is a set-system where no edge is a subset of any other. This sequence counts set-systems whose dual is a (strict) antichain, also called T_1 set-systems.

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

Set-systems are A058891.
T_0 set-systems are A326940.
The covering case is A326961.
The version with empty edges allowed is A326967.
Set-systems whose dual is a weak antichain are A326968.
The unlabeled version is A326972.
The BII_numbers of these set-systems are A326979.
Cf. A059052, A326951, A326966, A326970, A326971, A326976, A326977.

tmQ[eds_]:=Union@@Select[Intersection@@@Rest[Subsets[eds]],Length[#]==1&]==Union@@eds;
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],tmQ]],{n,0,3}]

Binomial transform of A326961.

a(n) = A326967(n)/2.

A326946 Number of unlabeled T_0 set-systems on n vertices.

Original entry on oeis.org

1, 2, 5, 34, 1919, 18660178

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			Non-isomorphic representatives of the a(0) = 1 through a(2) = 5 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{1},{2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

The non-T_0 version is A000612.
The antichain case is A245567.
The covering case is A319637.
The labeled version is A326940.
The version with empty edges allowed is A326949.
Cf. A003180, A055621, A059052, A059201, A316978, A319559, A319564, A326942.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Union[normclut/@Select[Subsets[Subsets[Range[n],{1,n}]],UnsameQ@@dual[#]&]]],{n,0,3}]

Partial sums of A319637.

a(n) = A326949(n)/2.

a(5) from Max Alekseyev, Oct 11 2023

A326961 Number of set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called covering T_1 set-systems.

Original entry on oeis.org

1, 1, 2, 36, 19020, 2010231696, 9219217412568364176, 170141181796805105960861096082778425120, 57896044618658097536026644159052312977171804852352892309392604715987334365792

Offset: 0

Gus Wiseman, Aug 12 2019

nonn

Same as A059523 except with a(1) = 1 instead of 2.

Alternatively, these are set-systems covering n vertices whose dual is a (strict) antichain. A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. An antichain is a set of sets, none of which is a subset of any other.

			The a(3) = 36 set-systems:
  {{1}{2}{3}}        {{12}{13}{23}{123}}     {{2}{3}{12}{13}{23}}
  {{12}{13}{23}}     {{1}{2}{3}{12}{13}}     {{2}{3}{12}{13}{123}}
  {{1}{2}{3}{12}}    {{1}{2}{3}{12}{23}}     {{2}{12}{13}{23}{123}}
  {{1}{2}{3}{13}}    {{1}{2}{3}{13}{23}}     {{3}{12}{13}{23}{123}}
  {{1}{2}{3}{23}}    {{1}{2}{12}{13}{23}}    {{1}{2}{3}{12}{13}{23}}
  {{1}{2}{13}{23}}   {{1}{2}{3}{12}{123}}    {{1}{2}{3}{12}{13}{123}}
  {{1}{2}{3}{123}}   {{1}{2}{3}{13}{123}}    {{1}{2}{3}{12}{23}{123}}
  {{1}{3}{12}{23}}   {{1}{2}{3}{23}{123}}    {{1}{2}{3}{13}{23}{123}}
  {{2}{3}{12}{13}}   {{1}{3}{12}{13}{23}}    {{1}{2}{12}{13}{23}{123}}
  {{1}{12}{13}{23}}  {{1}{2}{13}{23}{123}}   {{1}{3}{12}{13}{23}{123}}
  {{2}{12}{13}{23}}  {{1}{3}{12}{23}{123}}   {{2}{3}{12}{13}{23}{123}}
  {{3}{12}{13}{23}}  {{1}{12}{13}{23}{123}}  {{1}{2}{3}{12}{13}{23}{123}}

Covering set-systems are A003465.
Covering T_0 set-systems are A059201.
The version with empty edges allowed is A326960.
The non-covering version is A326965.
Covering set-systems whose dual is a weak antichain are A326970.
The unlabeled version is A326974.
The BII-numbers of T_1 set-systems are A326979.
Cf. A058891, A059052, A059523, A323818, A326972, A326973, A326976, A326977.

tmQ[eds_]:=Union@@Select[Intersection@@@Rest[Subsets[eds]],Length[#]==1&]==Union@@eds;
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&tmQ[#]&]],{n,0,3}]

Inverse binomial transform of A326965.

A059523 Number of n-element unlabeled ordered T_0-antichains without isolated vertices; number of T_1-hypergraphs (without empty edge and without multiple edges) on n labeled vertices.

Original entry on oeis.org

1, 2, 2, 36, 19020, 2010231696, 9219217412568364176, 170141181796805105960861096082778425120, 57896044618658097536026644159052312977171804852352892309392604715987334365792

Offset: 0

Vladeta Jovovic and Goran Kilibarda, Jan 20 2001; revised Jun 03 2004

nonn

			Number of k-element T_1-hipergraphs (without empty edge and without multiple edges) on 3 labeled vertices is
C(7,k)-6*C(5,k)+6*C(4,k)+3*C(3,k)-6*C(2,k)+2*C(1,k),k=0..7; so a(3)=2+11+15+7+1=36=2^7-6*2^5+6*2^4+3*2^3-6*2^2+2*2.

V. Jovovic, T_1-hyper graphs on a labeled 3-set
Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

Cf. A003465, A059201, A059052, A326961.

a(n) = A059052(n)/2.

A326970 Number of set-systems covering n vertices whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 3, 43, 19251

Offset: 0

Gus Wiseman, Aug 10 2019

A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edges 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}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

			The a(3) = 43 set-systems:
  {123}  {1}{23}  {1}{2}{3}     {1}{2}{3}{12}
         {2}{13}  {12}{13}{23}  {1}{2}{3}{13}
         {3}{12}  {1}{23}{123}  {1}{2}{3}{23}
                  {2}{13}{123}  {1}{2}{13}{23}
                  {3}{12}{123}  {1}{2}{3}{123}
                                {1}{3}{12}{23}
                                {2}{3}{12}{13}
                                {1}{12}{13}{23}
                                {2}{12}{13}{23}
                                {3}{12}{13}{23}
                                {12}{13}{23}{123}
.
  {1}{2}{3}{12}{13}     {1}{2}{3}{12}{13}{23}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{3}{12}{23}     {1}{2}{3}{12}{13}{123}
  {1}{2}{3}{13}{23}     {1}{2}{3}{12}{23}{123}
  {1}{2}{12}{13}{23}    {1}{2}{3}{13}{23}{123}
  {1}{2}{3}{12}{123}    {1}{2}{12}{13}{23}{123}
  {1}{2}{3}{13}{123}    {1}{3}{12}{13}{23}{123}
  {1}{2}{3}{23}{123}    {2}{3}{12}{13}{23}{123}
  {1}{3}{12}{13}{23}
  {2}{3}{12}{13}{23}
  {1}{2}{13}{23}{123}
  {1}{3}{12}{23}{123}
  {2}{3}{12}{13}{123}
  {1}{12}{13}{23}{123}
  {2}{12}{13}{23}{123}
  {3}{12}{13}{23}{123}

Covering set-systems are A003465.
Covering set-systems whose dual is strict are A059201.
The T_1 case is A326961.
The BII-numbers of these set-systems are A326966.
The non-covering case is A326968.
The unlabeled version is A326973.
Cf. A006126, A059052, A059523, A326950, A326960, A326965, A326969, A326971, A326974, A326975, A326978.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&stableQ[dual[#],SubsetQ]&]],{n,0,3}]

Inverse binomial transform of A326968.

A326943 Number of T_0 sets of subsets of {1..n} that cover all n vertices and are closed under intersection.

Original entry on oeis.org

2, 2, 6, 70, 4078, 2704780, 151890105214, 28175292217767880450

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			The a(0) = 2 through a(3) = 6 sets of subsets:
  {}    {{1}}     {{1},{1,2}}
  {{}}  {{},{1}}  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A326906.
The case without empty edges is A309615.
The non-covering version is A326945.
The version not closed under intersection is A326939.
Cf. A003180, A003181, A003465, A059052, A059201, A245567, A316978, A319564, A319637, A326940, A326941, A326942, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&UnsameQ@@dual[#]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

Inverse binomial transform of A326945.

a(n) = Sum_{k=0..n} Stirling1(n,k)*A326906(k). - Andrew Howroyd, Aug 14 2019

a(5)-a(7) from Andrew Howroyd, Aug 14 2019

A059048 Triangle A(n,m) of numbers of n-element ordered T_0-antichains on an unlabeled m-set or numbers of T_1-hypergraphs on n labeled nodes with m (not necessarily empty) distinct hyperedges (m=0,1,...,2^n).

Original entry on oeis.org

1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 0, 0, 0, 2, 13, 26, 22, 8, 1, 0, 0, 0, 0, 25, 354, 1798, 4822, 8028, 9044, 7240, 4224, 1808, 560, 120, 16, 1, 0, 0, 0, 0, 30, 2086, 45512, 461236, 2797785, 11669660, 36369970, 89356260, 179461250, 302225100, 43458923, 0

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Dec 19 2000

nonn

An antichain on a set is a T_0-antichain if for every two distinct points of the set there exists a member of the antichain containing one but not the other point. T_1-hypergraph is a hypergraph which for every ordered pair (u,v) of distinct nodes has a hyperedge containing u but not v.

			[1, 1], [1, 2, 1], [0, 0, 1, 2, 1], [0, 0, 0, 2, 13, 26, 22, 8, 1], .... There are 72 3-element unlabeled ordered T_0-antichains: 2 on 3-set, 13 on 4-set, 26 on 5-set, 22 on 6-set, 8 on 7-set and 1 on 8-set.

V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6)
V. Jovovic, G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.

V. Jovovic, 3-element unlabeled ordered T_0-antichains"
V. Jovovic, Number A(m,n) of m-element ordered T_0-antichains on an unlabeled n-set

Cf. A059049-A059052.

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Original entry on oeis.org

2, 4, 8, 40, 2464

Offset: 0

Gus Wiseman, Aug 13 2019

Alternatively, these are unlabeled sets of subsets of {1..n} whose dual is a (strict) antichain, also called T_1 sets of subsets. The dual of a set of subsets has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. An antichain is a set of subsets where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{},{1}}
                  {{1},{2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Unlabeled sets of subsets are A003180.
Unlabeled T_0 sets of subsets are A326949.
The labeled version is A326967.
The case without empty edges is A326972.
The covering case is A327011 (first differences).
Cf. A003181, A059052, A326960, A326965, A326969, A326974, A326976.

a(n) = 2 * A326972(n).

a(n) = Sum_{k = 0..n} A327011(k).

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

Original entry on oeis.org

2, 2, 4, 72, 38040, 4020463392, 18438434825136728352, 340282363593610211921722192165556850240, 115792089237316195072053288318104625954343609704705784618785209431974668731584

Offset: 0

Gus Wiseman, Aug 13 2019

nonn

Same as A059052 except with a(1) = 2 instead of 4.
The dual of a set of subsets 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}}. An antichain is a set of subsets where no edge is a subset of any other.
Alternatively, these are sets of subsets of {1..n} covering all n vertices where every vertex is the unique common element of some subset of the edges.

			The a(0) = 2 through a(2) = 4 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Covering sets of subsets are A000371.
Covering T_0 sets of subsets are A326939.
The case without empty edges is A326961.
The non-covering version is A326967.
Cf. A003181, A059052, A059523, A319639, A326951, A326965, A326974, A326976, A326977, A326979.

Table[Length[Select[Subsets[Subsets[Range[n]]],Length[Union[Select[Intersection@@@Rest[Subsets[#]],Length[#]==1&]]]==n&]],{n,0,3}]

Binomial transform of A326967.

A326969 Number of sets of subsets of {1..n} whose dual is a weak antichain.

Original entry on oeis.org

2, 4, 12, 112, 38892

Offset: 0

Gus Wiseman, Aug 10 2019

The dual of a set of subsets 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}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

			The a(0) = 2 through a(2) = 12 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{2}}
                  {{1,2}}
                  {{},{1}}
                  {{},{2}}
                  {{1},{2}}
                  {{},{1,2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Sets of subsets whose dual is strict are A326941.
The BII-numbers of set-systems whose dual is a weak antichain are A326966.
Sets of subsets whose dual is a (strict) antichain are A326967.
The case without empty edges is A326968.
Cf. A001146, A059052, A326951, A326970, A326971, A326975, A326978.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n]]],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

a(n) = 2 * A326968(n).

a(n) = 2 * Sum_{k = 0..n} binomial(n, k) * A326970(k).

cp's OEIS Frontend

A326965 Number of set-systems on n vertices where every covered vertex is the unique common element of some subset of the edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326946 Number of unlabeled T_0 set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326961 Number of set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called covering T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A059523 Number of n-element unlabeled ordered T_0-antichains without isolated vertices; number of T_1-hypergraphs (without empty edge and without multiple edges) on n labeled vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A326970 Number of set-systems covering n vertices whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326943 Number of T_0 sets of subsets of {1..n} that cover all n vertices and are closed under intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A059048 Triangle A(n,m) of numbers of n-element ordered T_0-antichains on an unlabeled m-set or numbers of T_1-hypergraphs on n labeled nodes with m (not necessarily empty) distinct hyperedges (m=0,1,...,2^n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

Views