A326947 -id:A326947 - cp's OEIS frontend

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

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

A326950 Number of T_0 antichains of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 2, 4, 12, 107, 6439, 7726965, 2414519001532, 56130437161079183223017, 286386577668298409107773412840148848120595

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).

			The a(0) = 1 through a(3) = 12 antichains:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1},{2}}  {{3}}
                        {{1},{2}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1,2},{1,3}}
                        {{1,2},{2,3}}
                        {{1},{2},{3}}
                        {{1,3},{2,3}}
                        {{1,2},{1,3},{2,3}}

Antichains of nonempty sets are A014466.
T_0 set-systems are A326940.
The covering case is A245567.
Cf. A006126, A059201, A059052, A245567, A319559, A319564, A326030, A326946, A326947.

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}]],stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}]

Binomial transform of A245567, if we assume A245567(0) = 1.

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

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

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 3, 62, 24710, 2076948136, 9221293198653529144, 170141182628636920684331812494864430896

Offset: 0

Gus Wiseman, Aug 18 2019

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 covering set-systems whose dual is strict and pairwise intersecting.

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

The pairwise intersecting case is A319774.
The BII-numbers of these set-systems are the intersection of A326947 and A326853.
The non-T_0 version is A327040.
The non-covering version is A327052.
Cf. A003465, A305843, A319767, A326854, A327020, A327037, A327039.

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

Inverse binomial transform of A327052.

a(5)-a(7) from Christian Sievers, Feb 04 2024

A326854 BII-numbers of T_0 (costrict), pairwise intersecting set-systems where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

0, 1, 2, 5, 6, 8, 17, 24, 34, 40, 52, 69, 70, 81, 84, 85, 88, 98, 100, 102, 104, 112, 116, 120, 128, 257, 384, 514, 640, 772, 1029, 1030, 1281, 1284, 1285, 1408, 1538, 1540, 1542, 1664, 1792, 1796, 1920, 2056, 2176, 2320, 2592, 2880, 3120, 3152, 3168, 3184

Offset: 1

Gus Wiseman, Aug 18 2019

nonn

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 gives all BII-numbers (defined below) of pairwise intersecting set-systems whose dual is strict and pairwise intersecting.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			The sequence of all set-systems that are pairwise intersecting, cointersecting, and costrict, together with their BII-numbers, begins:
    0: {}
    1: {{1}}
    2: {{2}}
    5: {{1},{1,2}}
    6: {{2},{1,2}}
    8: {{3}}
   17: {{1},{1,3}}
   24: {{3},{1,3}}
   34: {{2},{2,3}}
   40: {{3},{2,3}}
   52: {{1,2},{1,3},{2,3}}
   69: {{1},{1,2},{1,2,3}}
   70: {{2},{1,2},{1,2,3}}
   81: {{1},{1,3},{1,2,3}}
   84: {{1,2},{1,3},{1,2,3}}
   85: {{1},{1,2},{1,3},{1,2,3}}
   88: {{3},{1,3},{1,2,3}}
   98: {{2},{2,3},{1,2,3}}
  100: {{1,2},{2,3},{1,2,3}}
  102: {{2},{1,2},{2,3},{1,2,3}}

Equals the intersection of A326947, A326910, and A326853.
These set-systems are counted by A319774 (covering).
The non-T_0 version is A327061.
Cf. A029931, A048793, A051185, A305843, A319765, A326031, A327037, A327038, A327041, A327052, A327053.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,10000],UnsameQ@@dual[bpe/@bpe[#]]&&stableQ[bpe/@bpe[#],Intersection[#1,#2]=={}&]&&stableQ[dual[bpe/@bpe[#]],Intersection[#1,#2]=={}&]&]

A326959 Number of T_0 set-systems covering a subset of {1..n} that are closed under intersection.

Original entry on oeis.org

1, 2, 5, 22, 297, 20536, 16232437, 1063231148918, 225402337742595309857

Offset: 0

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

			The a(0) = 1 through a(3) = 22 set-systems:
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{2}}        {{2}}
             {{1},{1,2}}  {{3}}
             {{2},{1,2}}  {{1},{1,2}}
                          {{1},{1,3}}
                          {{2},{1,2}}
                          {{2},{2,3}}
                          {{3},{1,3}}
                          {{3},{2,3}}
                          {{1},{1,2},{1,3}}
                          {{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 covering case is A309615.
T_0 set-systems are A326940.
The version with empty edges allowed is A326945.
Cf. A051185, A058891, A059201, A316978, A319559, A309615, A319637, A326943, A326944, A326946, A326947, A326959.

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

Binomial transform of A309615.

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

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 10, 97, 2160, 126862, 21485262, 11105374322, 18109358131513, 95465831661532570, 1660400673336788987026, 96929369602251313489896310, 19268528295096123543660356281600, 13203875101002459910158494602665950757, 31517691852305548841992346407978317698725021

Offset: 0

Gus Wiseman, Jan 07 2024

nonn

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

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

The case of graphs is A001434, labeled A116508.
Labeled version is A136556, covering A054780, binomial transform of A367916.
The case of labeled covering graphs is A367863, binomial transform A367862.
These include the set-systems ranked by A367917.
The covering case is A368186, for graphs A006649, connected A057500.
Requiring all edges to be singletons or pairs gives A368598.
A003465 counts covers with any number of edges, 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, A007716, A283877, A367901, A367902, A367903, A368599.

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

a(n) = polcoef(G(n, n), n) \\ G defined in A368186. - Andrew Howroyd, Jan 11 2024

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

A326948 Number of connected T_0 set-systems on n vertices.

Original entry on oeis.org

1, 1, 3, 86, 31302, 2146841520, 9223371978880250448, 170141183460469231408869283342774399392, 57896044618658097711785492504343953919148780260559635830120038252613826101856

Offset: 0

Gus Wiseman, Aug 08 2019

nonn

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(3) = 86 set-systems:
  {12}{13}         {1}{2}{13}{123}     {1}{2}{3}{13}{23}
  {12}{23}         {1}{2}{23}{123}     {1}{2}{3}{13}{123}
  {13}{23}         {1}{3}{12}{13}      {1}{2}{3}{23}{123}
  {1}{2}{123}      {1}{3}{12}{23}      {1}{2}{12}{13}{23}
  {1}{3}{123}      {1}{3}{12}{123}     {1}{2}{12}{13}{123}
  {1}{12}{13}      {1}{3}{13}{23}      {1}{2}{12}{23}{123}
  {1}{12}{23}      {1}{3}{13}{123}     {1}{2}{13}{23}{123}
  {1}{12}{123}     {1}{3}{23}{123}     {1}{3}{12}{13}{23}
  {1}{13}{23}      {1}{12}{13}{23}     {1}{3}{12}{13}{123}
  {1}{13}{123}     {1}{12}{13}{123}    {1}{3}{12}{23}{123}
  {2}{3}{123}      {1}{12}{23}{123}    {1}{3}{13}{23}{123}
  {2}{12}{13}      {1}{13}{23}{123}    {1}{12}{13}{23}{123}
  {2}{12}{23}      {2}{3}{12}{13}      {2}{3}{12}{13}{23}
  {2}{12}{123}     {2}{3}{12}{23}      {2}{3}{12}{13}{123}
  {2}{13}{23}      {2}{3}{12}{123}     {2}{3}{12}{23}{123}
  {2}{23}{123}     {2}{3}{13}{23}      {2}{3}{13}{23}{123}
  {3}{12}{13}      {2}{3}{13}{123}     {2}{12}{13}{23}{123}
  {3}{12}{23}      {2}{3}{23}{123}     {3}{12}{13}{23}{123}
  {3}{13}{23}      {2}{12}{13}{23}     {1}{2}{3}{12}{13}{23}
  {3}{13}{123}     {2}{12}{13}{123}    {1}{2}{3}{12}{13}{123}
  {3}{23}{123}     {2}{12}{23}{123}    {1}{2}{3}{12}{23}{123}
  {12}{13}{23}     {2}{13}{23}{123}    {1}{2}{3}{13}{23}{123}
  {12}{13}{123}    {3}{12}{13}{23}     {1}{2}{12}{13}{23}{123}
  {12}{23}{123}    {3}{12}{13}{123}    {1}{3}{12}{13}{23}{123}
  {13}{23}{123}    {3}{12}{23}{123}    {2}{3}{12}{13}{23}{123}
  {1}{2}{3}{123}   {3}{13}{23}{123}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{12}{13}   {12}{13}{23}{123}
  {1}{2}{12}{23}   {1}{2}{3}{12}{13}
  {1}{2}{12}{123}  {1}{2}{3}{12}{23}
  {1}{2}{13}{23}   {1}{2}{3}{12}{123}

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

The same with covering instead of connected is A059201, with unlabeled version A319637.
The non-T_0 version is A323818 (covering) or A326951 (not-covering).
The non-connected version is A326940, with unlabeled version A326946.
Cf. A000371, A003465, A245567, A316978, A319559, A319564, A326939, A326941, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&UnsameQ@@dual[#]&]],{n,0,3}]

Logarithmic transform of A059201.

A327016 BII-numbers of finite T_0 topologies without their empty set.

Original entry on oeis.org

0, 1, 2, 5, 6, 7, 8, 17, 24, 25, 34, 40, 42, 69, 70, 71, 81, 85, 87, 88, 89, 93, 98, 102, 103, 104, 106, 110, 120, 121, 122, 127, 128, 257, 384, 385, 514, 640, 642, 1029, 1030, 1031, 1281, 1285, 1287, 1408, 1409, 1413, 1538, 1542, 1543, 1664, 1666, 1670, 1920

Offset: 1

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

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of all finite T_0 topologies without their empty set together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}
  81: {{1},{1,3},{1,2,3}}
  85: {{1},{1,2},{1,3},{1,2,3}}
  87: {{1},{2},{1,2},{1,3},{1,2,3}}
  88: {{3},{1,3},{1,2,3}}

Gus Wiseman, The first 100 finite T_0 topologies, represented as posets.

T_0 topologies are A001035, with unlabeled version A000112.
BII-numbers of topologies without their empty set are A326876.
BII-numbers of T_0 set-systems are A326947.
Cf. A001930, A048793, A306445, A316978, A319564, A326031, A326872, A326875, A326939, A326941, A326959.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,1000],UnsameQ@@dual[bpe/@bpe[#]]&&SubsetQ[bpe/@bpe[#],Union[Union@@@Tuples[bpe/@bpe[#],2],DeleteCases[Intersection@@@Tuples[bpe/@bpe[#],2],{}]]]&]

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326950 Number of T_0 antichains of nonempty subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326854 BII-numbers of T_0 (costrict), pairwise intersecting set-systems where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326959 Number of T_0 set-systems covering a subset of {1..n} that are closed under intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A326948 Number of connected T_0 set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A327016 BII-numbers of finite T_0 topologies without their empty set.

Views

Author