A319637 -id:A319637 - cp's OEIS frontend

A326939 Number of T_0 sets of subsets of {1..n} that cover all n vertices.

2, 2, 8, 192, 63384, 4294003272, 18446743983526539408, 340282366920938462946865774750753349904, 115792089237316195423570985008687907841019819456486779364848020385134373080448

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. 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(2) = 8 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{1},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A000371.
The case without empty edges is A059201.
The non-covering version is A326941.
The unlabeled version is A326942.
The case closed under intersection is A326943.
Cf. A003180, A003181, A003465, A316978, A319564, A319637, A326940, A326947.

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

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

Inverse binomial transform of A326941.

A326972 Number of unlabeled set-systems on n vertices whose dual is a (strict) antichain, also called unlabeled T_1 set-systems.

Original entry on oeis.org

1, 2, 4, 20, 1232

Offset: 0

Gus Wiseman, Aug 11 2019

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 of sets, none of which is a subset of any other.

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

Unlabeled set-systems are A000612.
Unlabeled set-systems whose dual is strict are A326946.
The version with empty edges allowed is A326951.
The labeled version is A326965.
The version where the dual is not required to be strict is A326971.
The covering version is A326974 (first differences).
Cf. A059523, A319559, A319637, A326973, A326976, A326977, A326979.

A326941 Number of T_0 sets of subsets of {1..n}.

Original entry on oeis.org

2, 4, 14, 224, 64210, 4294322204, 18446744009291513774, 340282366920938463075992982725615419816, 115792089237316195423570985008687907843742078391854287068939455414919611614210

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. 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(2) = 14 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{2}}
                  {{},{1}}
                  {{},{2}}
                  {{1},{2}}
                  {{1},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A001146.
The covering case is A326939.
The case without empty edges is A326940.
The unlabeled version is A326949.
Cf. A003180, A059201, A316978, A319559, A319564, A319637, A326946, A326947.

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

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

Binomial transform of A326939.

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

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

Original entry on oeis.org

1, 1, 3, 19, 1243

Offset: 0

Gus Wiseman, Aug 11 2019

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

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

Unlabeled covering set-systems are A055621.
The labeled version is A326970.
The non-covering case is A326971 (partial sums).
The case that is also T_0 is the T_1 case A326974.
Cf. A000612, A059523, A319637, A326966, A326968, A326972, A326975, A326978.

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Original entry on oeis.org

2, 1, 1, 5, 76, 5993, 7689745, 2414465044600, 56130437141763247212112, 286386577668298408602599478477358234902247

Offset: 0

Patrick De Causmaecker, Jul 25 2014

This is the number of antichain covers such that the induced partition contains only singletons. The induced partition of {{1,2},{2,3},{1,3},{3,4}} is {{1},{2},{3},{4}}, while the induced partition of {{1,2,3},{2,3,4}} is {{1},{2,3},{4}}.
This sequence is related to A006126. See 1st formula.
The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
Sets of subsets of the described type are said to be T_0. - Gus Wiseman, Aug 14 2019

			For n = 0, a(0) = 2 by the antisets {}, {{}}.
For n = 1, a(1) = 1 by the antiset {{1}}.
For n = 2, a(2) = 1 by the antiset {{1},{2}}.
For n = 3, a(3) = 5 by the antisets {{1},{2},{3}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1,2},{1,3},{2,3}}.

Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).
Sequences counting and ranking T_0 structures:
  A000112 (unlabeled topologies),
  A001035 (topologies),
  A059201 (covering set-systems),
  A245567 (antichain covers),
  A309615 (covering set-systems closed under intersection),
  A316978 (factorizations),
  A319559 (unlabeled set-systems by weight),
  A319564 (integer partitions),
  A319637 (unlabeled covering set-systems),
  A326939 (covering sets of subsets),
  A326940 (set-systems),
  A326941 (sets of subsets),
  A326943 (covering sets of subsets closed under intersection),
  A326944 (covering sets of subsets with {} and closed under intersection),
  A326945 (sets of subsets closed under intersection),
  A326946 (unlabeled set-systems),
  A326947 (BII-numbers of set-systems),
  A326948 (connected set-systems),
  A326949 (unlabeled sets of subsets),
  A326950 (antichains),
  A326959 (set-systems closed under intersection),
  A327013 (unlabeled covering set-systems closed under intersection),
  A327016 (BII-numbers of topologies).

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]]],Union@@#==Range[n]&&stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 14 2019 *)

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
a(n) = A006126(n) - Sum_{k=1..n-1} S(n,k)*a(k).
Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
Inverse binomial transform of A326950, if we assume a(0) = 1. - Gus Wiseman, Aug 14 2019

Definition corrected by Patrick De Causmaecker, Oct 10 2014

a(9), based on A000372, from Patrick De Causmaecker, Jun 01 2023

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

A368186 Number of n-covers of an unlabeled n-set.

Original entry on oeis.org

1, 1, 2, 9, 87, 1973, 118827, 20576251, 10810818595, 17821875542809, 94589477627232498, 1651805220868992729874, 96651473179540769701281003, 19238331716776641088273777321428, 13192673305726630096303157068241728202, 31503323006770789288222386469635474844616195

Offset: 0

Gus Wiseman, Dec 19 2023

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50

The labeled version is A054780, ranks A367917, non-covering A367916.
The case of graphs is A006649, labeled A367863, cf. A116508, A367862.
The case of connected graphs is A001429, labeled A057500.
Covers with any number of edges are counted by A003465, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A002494, A006126, A055130, A133686, A140638, A305000, A317795, A326754, A367901, A367902, A367903.

brute[m_]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}];
Table[Length[Union[First[Sort[brute[#]]]& /@ Select[Subsets[Rest[Subsets[Range[n]]],{n}], Union@@#==Range[n]&]]], {n,0,3}]

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t)={2^sum(j=1, #q, gcd(t, q[j])) - 1}
G(n,m)={if(n==0, 1, my(s=0); forpart(q=n, my(g=sum(t=1, m, K(q,t)*x^t/t, O(x*x^m))); s+=permcount(q)*exp(g - subst(g,x,x^2))); s/n!)}
a(n)=if(n ==0, 1, polcoef(G(n,n) - G(n-1,n), n)) \\ Andrew Howroyd, Jan 03 2024

a(n) = A055130(n, n) for n > 0. - Andrew Howroyd, Jan 03 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 03 2024

A326949 Number of unlabeled T_0 sets of subsets of {1..n}.

Original entry on oeis.org

2, 4, 10, 68, 3838, 37320356

Offset: 0

Gus Wiseman, Aug 08 2019

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}}. The T_0 condition means that the dual is strict (no repeated edges).

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

The non-T_0 version is A003180.
The labeled version is A326941.
The covering case is A326942 (first differences).
The case without empty edges is A326946.
Cf. A000371, A000612, A003181, A059052, A245567, A316978, A319559, A319564, A319637, A326939, A326940.

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

a(5) from Max Alekseyev, Oct 11 2023

A330282 Number of fully chiral set-systems on n vertices.

Original entry on oeis.org

1, 2, 5, 52, 21521

Offset: 0

Gus Wiseman, Dec 10 2019

A set-system is a finite set of finite nonempty sets. It is fully chiral if every permutation of the covered vertices gives a different representative.

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

Costrict (or T_0) set-systems are A326940.
The covering case is A330229.
The unlabeled version is A330294, with covering case A330295.
Achiral set-systems are A083323.
BII-numbers of fully chiral set-systems are A330226.
Non-isomorphic fully chiral multiset partitions are A330227.
Fully chiral partitions are A330228.
Fully chiral factorizations are A330235.
MM-numbers of fully chiral multisets of multisets are A330236.
Cf. A000612, A016031, A319637, A330098, A330231, A330232, A330234.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Length[graprms[#]]==Length[Union@@#]!&]],{n,0,3}]

Binomial transform of A330229.

A309615 Number of T_0 set-systems covering n vertices that are closed under intersection.

Original entry on oeis.org

1, 1, 2, 12, 232, 19230, 16113300, 1063117943398, 225402329237199496416

Offset: 0

Gus Wiseman, Aug 11 2019

First differs from A182507 at a(5) = 19230, A182507(5) = 12848.

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}}. The T_0 condition means that the dual is strict (no repeated edges).

			The a(0) = 1 through a(3) = 12 set-systems:
  {}  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
             {{2},{1,2}}  {{2},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,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},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}

The version with empty edges allowed is A326943.

Cf. A003465, A059052, A059201, A319637, A326880, A326881, A326901, A326902, A326905, A326944, A326945.

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

a(n) = A326943(n) - A326944(n).
a(n) = Sum_{k = 1..n} s(n,k) * A326901(k - 1) where s = A048994.
a(n) = Sum_{k = 1..n} s(n,k) * A326902(k) where s = A048994.

cp's OEIS Frontend

A326939 Number of T_0 sets of subsets of {1..n} that cover all n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326972 Number of unlabeled set-systems on n vertices whose dual is a (strict) antichain, also called unlabeled T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

A326941 Number of T_0 sets of subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A368186 Number of n-covers of an unlabeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326949 Number of unlabeled T_0 sets of subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions