A326883 -id:A326883 - cp's OEIS frontend

A102894 Number of ACI algebras or semilattices on n generators, with no identity or annihilator.

1, 1, 4, 45, 2271, 1373701, 75965474236, 14087647703920103947

Offset: 0

Mitch Harris, Jan 18 2005

Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain both the universe and the empty set.
An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
Also the number of set-systems covering n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - Gus Wiseman, Aug 01 2019
Number of strict closure operators on a set of n elements, where the closure operator is said to be strict if the empty set is closed. - Tian Vlasic, Jul 30 2022

			From _Gus Wiseman_, Aug 01 2019: (Start)
The a(3) = 45 set-systems with {} and {1,2,3} that are closed under intersection are the following ({} and {1,2,3} not shown). The BII-numbers of these set-systems are given by A326880.
0   {1}   {1}{2}   {1}{2}{3}    {1}{2}{3}{12}   {1}{2}{3}{12}{13}
    {2}   {1}{3}   {1}{2}{12}   {1}{2}{3}{13}   {1}{2}{3}{12}{23}
    {3}   {2}{3}   {1}{2}{13}   {1}{2}{3}{23}   {1}{2}{3}{13}{23}
    {12}  {1}{12}  {1}{2}{23}   {1}{2}{12}{13}
    {13}  {1}{13}  {1}{3}{12}   {1}{2}{12}{23}
    {23}  {1}{23}  {1}{3}{13}   {1}{3}{12}{13}        {1}{2}{3}{12}{13}{23}
          {2}{12}  {1}{3}{23}   {1}{3}{13}{23}
          {2}{13}  {2}{3}{12}   {2}{3}{12}{23}
          {2}{23}  {2}{3}{13}   {2}{3}{13}{23}
          {3}{12}  {2}{3}{23}
          {3}{13}  {1}{12}{13}
          {3}{23}  {2}{12}{23}
                   {3}{13}{23}
(End)

G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.
E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

Maria Paola Bonacina and Nachum Dershowitz, Canonical ground Horn theories, Lecture Notes in Computer Science 7797, 35-71 (2013).
P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010).
N. Dershowitz, G. S. Huang and M. Harris, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
Christopher S. Flippen, Minimal Sets, Union-Closed Families, and Frankl's Conjecture, Master's thesis, Virginia Commonwealth Univ., 2023.
M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

Regarding set-systems covering n vertices closed under union:
- The non-covering case is A102896.
- The BII-numbers of these set-systems are A326875.
- The case with intersection instead of union is A326881.
- The unlabeled case is A108798.
Cf. A003465, A072447, A102895, A102897, A108800, A193674, A193675, A306445, A326870, A326880, A326883.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* Gus Wiseman, Aug 01 2019 *)

Inverse binomial transform of A102896.

For asymptotics see A102897.

Additional comments from Don Knuth, Jul 01 2005

A102895 Number of ACI algebras or semilattices on n generators with no identity element.

Original entry on oeis.org

1, 2, 8, 90, 4542, 2747402, 151930948472, 28175295407840207894

Offset: 0

Mitch Harris, Jan 18 2005

An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.

Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain the empty set.

			a(2) = 8: Let the points be labeled a, b and let 0 denote the empty set. We want the number of collections of subsets of {a, b} which are closed under intersection and contain the empty subset. 0 subsets: 0 ways, 1 subset: 1 way (0), 2 subsets: 3 ways (0,a; 0,b; 0,ab), 3 subsets: 3 ways (0,a,b; 0,a,ab; 0,b,ab), 4 subsets: 1 way (0,a,b,ab), for a total of 8.
From _Gus Wiseman_, Aug 02 2019: (Start)
The a(0) = 1 through a(2) = 8 sets of sets with {} that are closed under intersection are:
  {{}}  {{}}      {{}}
        {{},{1}}  {{},{1}}
                  {{},{2}}
                  {{},{1,2}}
                  {{},{1},{2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)

G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.
P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

N. Dershowitz, G. S. Huang and M. Harris, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

The connected case (i.e., with maximum) is A102894.
The same for union instead of intersection is A102896.
The unlabeled version is A108800.
The case also closed under union is A326878.
The BII-numbers of these set-systems (without the empty set) are A326880.
The covering case is A326881.
Cf. A000798, A102897, A108798, A193674, A193675, A306445, A326883.

Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}] (* Gus Wiseman, Aug 02 2019 *)

For asymptotics see A102897.

a(n > 0) = 2 * A102894(n).

Additional comments from Don Knuth, Jul 01 2005

Changed a(0) from 2 to 1 by Gus Wiseman, Aug 02 2019

A193674 Number of nonisomorphic systems enumerated by A102896; that is, the number of inequivalent closure operators (or Moore families).

Original entry on oeis.org

1, 2, 5, 19, 184, 14664, 108295846, 2796163199765896

Offset: 0

Don Knuth, Jul 01 2005

Also the number of unlabeled n-vertex set-systems (A003180) closed under union. - Gus Wiseman, Aug 01 2019

			From _Gus Wiseman_, Aug 01 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(3) = 19 set-systems closed under union:
  {}  {}     {}               {}
      {{1}}  {{1}}            {{1}}
             {{1,2}}          {{1,2}}
             {{2},{1,2}}      {{1,2,3}}
             {{1},{2},{1,2}}  {{2},{1,2}}
                              {{3},{1,2,3}}
                              {{1},{2},{1,2}}
                              {{2,3},{1,2,3}}
                              {{1},{2,3},{1,2,3}}
                              {{3},{2,3},{1,2,3}}
                              {{1,3},{2,3},{1,2,3}}
                              {{2},{3},{2,3},{1,2,3}}
                              {{2},{1,3},{2,3},{1,2,3}}
                              {{3},{1,3},{2,3},{1,2,3}}
                              {{1,2},{1,3},{2,3},{1,2,3}}
                              {{2},{3},{1,3},{2,3},{1,2,3}}
                              {{3},{1,2},{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}}
(End)

D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1

Daniel Borchmann, Bernhard Ganter, Concept Lattice Orbifolds - First Steps, Proceedings of the 7th International Conference on Formal Concept Analysis (ICFCA 2009), 22-37 (Reference points to A108799).
G. Brinkmann and R. Deklerck, Generation of Union-Closed Sets and Moore Families, arXiv:1701.03751 [math.CO], 2017.
G. Brinkmann and R. Deklerck, Generation of Union-Closed Sets and Moore Families, Journal of Integer Sequences, Vol.21 (2018), Article 18.1.7.
P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010).

Cf. A102894, A102895, A102897.
The labeled case is A102896.
The covering case is A108798.
The same for intersection instead of union is A108800.
The case with empty edges allowed is A193675.
Cf. A000612, A001930, A003180, A306445, A326875, A326883.

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

a(6) received Aug 17 2005
a(6) corrected by Pierre Colomb, Aug 02 2011
a(7) from Gunnar Brinkmann, Feb 07 2018

A108798 Number of nonisomorphic systems enumerated by A102894; that is, the number of inequivalent closure operators in which the empty set is closed. Also, the number of union-closed sets with n elements that contain the universe and the empty set.

Original entry on oeis.org

1, 1, 3, 14, 165, 14480, 108281182, 2796163091470050

Offset: 0

Don Knuth, Jul 01 2005

Also the number of unlabeled finite sets of subsets of {1..n} that contain {} and {1..n} and are closed under intersection. - Gus Wiseman, Aug 02 2019

			From _Gus Wiseman_, Aug 02 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(3) = 14 union-closed sets of sets:
  {}  {}{1}  {}{12}        {}{123}
             {}{2}{12}     {}{3}{123}
             {}{1}{2}{12}  {}{23}{123}
                           {}{1}{23}{123}
                           {}{3}{23}{123}
                           {}{13}{23}{123}
                           {}{2}{3}{23}{123}
                           {}{2}{13}{23}{123}
                           {}{3}{13}{23}{123}
                           {}{12}{13}{23}{123}
                           {}{2}{3}{13}{23}{123}
                           {}{3}{12}{13}{23}{123}
                           {}{2}{3}{12}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}{123}
(End)

Maria Paola Bonacina and Nachum Dershowitz, Canonical ground Horn theories, Lecture Notes in Computer Science 7797, 35-71 (2013).
G. Brinkmann and R. Deklerck, Generation of Union-Closed Sets and Moore Families, Journal of Integer Sequences, Vol.21 (2018), Article 18.1.7.
G. Brinkmann and R. Deklerck, Generation of Union-Closed Sets and Moore Families, arXiv:1701.03751 [math.CO], 2017.
Christopher S. Flippen, Minimal Sets, Union-Closed Families, and Frankl's Conjecture, Master's thesis, Virginia Commonwealth Univ., 2023.

The labeled version is A102894.

Cf. A000612, A001930, A003180, A102895, A102897, A108800, A193674, A193675, A326867, A326869, A326883.

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

a(6) added (using A193674) by N. J. A. Sloane, Aug 02 2011

Added a(7), and reference to union-closed sets. - Gunnar Brinkmann, Feb 05 2018

A108800 Number of nonisomorphic systems enumerated by A102895.

Original entry on oeis.org

1, 2, 6, 28, 330, 28960, 216562364, 5592326182940100

Offset: 0

Don Knuth, Jul 01 2005

Also the number of non-isomorphic sets of sets with {} that are closed under intersection. Also the number of non-isomorphic set-systems (without {}) covering n + 1 vertices and closed under intersection. - Gus Wiseman, Aug 05 2019

			From _Gus Wiseman_, Aug 02 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(3) = 28 sets of sets with {} that are closed under intersection:
  {}  {}     {}            {}
      {}{1}  {}{1}         {}{1}
             {}{12}        {}{12}
             {}{1}{2}      {}{123}
             {}{2}{12}     {}{1}{2}
             {}{1}{2}{12}  {}{1}{23}
                           {}{2}{12}
                           {}{3}{123}
                           {}{1}{2}{3}
                           {}{23}{123}
                           {}{1}{2}{12}
                           {}{1}{3}{23}
                           {}{2}{3}{123}
                           {}{3}{13}{23}
                           {}{1}{23}{123}
                           {}{3}{23}{123}
                           {}{1}{2}{3}{23}
                           {}{1}{2}{3}{123}
                           {}{2}{3}{13}{23}
                           {}{1}{3}{23}{123}
                           {}{2}{3}{23}{123}
                           {}{3}{13}{23}{123}
                           {}{1}{2}{3}{13}{23}
                           {}{1}{2}{3}{23}{123}
                           {}{2}{3}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}
                           {}{1}{2}{3}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}{123}
(End)

M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

Except a(0) = 1, first differences of A193675.
The connected case (i.e., with maximum) is A108798.
The same for union instead of intersection is (also) A108798.
The labeled version is A102895.
The case also closed under union is A326898.
The covering case is A326883.
Cf. A001930, A102894, A102896, A102897, A193674, A326880, A326881.

a(n > 0) = 2 * A108798(n).

a(6) added (using A193675) by N. J. A. Sloane, Aug 02 2011
Changed a(0) from 2 to 1 by Gus Wiseman, Aug 02 2019
a(7) added (using A108798) by Andrew Howroyd, Aug 10 2019

A326881 Number of set-systems with {} that are closed under intersection and cover n vertices.

Original entry on oeis.org

1, 1, 5, 71, 4223, 2725521, 151914530499, 28175294344381108057

Offset: 0

Gus Wiseman, Jul 30 2019

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

The case also closed under union is A000798.
The connected case (i.e., with maximum) is A102894.
The same for union instead of intersection is (also) A102894.
The non-covering case is A102895.
The BII-numbers of these set-systems (without the empty set) are A326880.
The unlabeled case is A326883.
Cf. A003465, A014466, A102896, A102897, A193674, A193675, A306445, A307249, A326878.

Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&Union@@#==Range[n]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

Inverse binomial transform of A102895. - Andrew Howroyd, Aug 10 2019

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

A326906 Number of sets of subsets of {1..n} that are closed under union and cover all n vertices.

Original entry on oeis.org

2, 2, 8, 90, 4542, 2747402, 151930948472, 28175295407840207894

Offset: 0

Gus Wiseman, Aug 03 2019

Differs from A102895 in having a(0) = 2 instead of 1.

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

The case without empty sets is A102894.
The case with a single covering edge is A102895.
Binomial transform is A102897.
The case also closed under intersection is A326878 for n > 0.
The same for intersection instead of union is (also) A326906.
The unlabeled version is A326907.
Cf. A000798, A102896, A102897, A108800, A193675, A306445, A326880, A326881, A326883.

Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}]

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

A326907 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and cover all n vertices. First differences of A193675.

Original entry on oeis.org

2, 2, 6, 28, 330, 28960, 216562364, 5592326182940100

Offset: 0

Gus Wiseman, Aug 03 2019

Differs from A108800 in having a(0) = 2 instead of 1.

			Non-isomorphic representatives of the a(0) = 2 through a(3) = 28 sets of sets:
  {}    {{1}}    {{12}}          {{123}}
  {{}}  {{}{1}}  {{}{12}}        {{}{123}}
                 {{2}{12}}       {{3}{123}}
                 {{}{2}{12}}     {{23}{123}}
                 {{1}{2}{12}}    {{}{3}{123}}
                 {{}{1}{2}{12}}  {{}{23}{123}}
                                 {{1}{23}{123}}
                                 {{3}{23}{123}}
                                 {{13}{23}{123}}
                                 {{}{1}{23}{123}}
                                 {{}{3}{23}{123}}
                                 {{}{13}{23}{123}}
                                 {{2}{3}{23}{123}}
                                 {{2}{13}{23}{123}}
                                 {{3}{13}{23}{123}}
                                 {{12}{13}{23}{123}}
                                 {{}{2}{3}{23}{123}}
                                 {{}{2}{13}{23}{123}}
                                 {{}{3}{13}{23}{123}}
                                 {{}{12}{13}{23}{123}}
                                 {{2}{3}{13}{23}{123}}
                                 {{3}{12}{13}{23}{123}}
                                 {{}{2}{3}{13}{23}{123}}
                                 {{}{3}{12}{13}{23}{123}}
                                 {{2}{3}{12}{13}{23}{123}}
                                 {{}{2}{3}{12}{13}{23}{123}}
                                 {{1}{2}{3}{12}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}{123}}

The case without empty sets is A108798.
The case with a single covering edge is A108800.
First differences of A193675.
The case also closed under intersection is A326898 for n > 0.
The labeled version is A326906.
The same for union instead of intersection is (also) A326907.
Cf. A001930, A102895, A108798, A193674, A193675, A326880, A326881, A326883, A326898, A326908.

a(7) added from A108800 by Andrew Howroyd, Aug 10 2019

A326908 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and intersection.

Original entry on oeis.org

2, 4, 9, 23, 70, 256, 1160, 6599, 48017, 452518, 5574706, 90198548, 1919074899, 53620291147, 1962114118390, 93718030190126, 5822768063787557

Offset: 0

Gus Wiseman, Aug 03 2019

			Non-isomorphic representatives of the a(0) = 2 through a(3) = 23 sets of subsets:
  {}    {}       {}              {}
  {{}}  {{}}     {{}}            {{}}
        {{1}}    {{1}}           {{1}}
        {{}{1}}  {{12}}          {{12}}
                 {{}{1}}         {{}{1}}
                 {{}{12}}        {{123}}
                 {{2}{12}}       {{}{12}}
                 {{}{2}{12}}     {{}{123}}
                 {{}{1}{2}{12}}  {{2}{12}}
                                 {{3}{123}}
                                 {{}{2}{12}}
                                 {{23}{123}}
                                 {{}{3}{123}}
                                 {{}{23}{123}}
                                 {{}{1}{2}{12}}
                                 {{3}{23}{123}}
                                 {{}{1}{23}{123}}
                                 {{}{3}{23}{123}}
                                 {{3}{13}{23}{123}}
                                 {{}{2}{3}{23}{123}}
                                 {{}{3}{13}{23}{123}}
                                 {{}{2}{3}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}{123}}

The labeled version is A306445.
Taking first differences and prepending 1 gives A326898.
Taking second differences and prepending two 1's gives A001930.
Cf. A000612, A000798, A003180, A108798, A108800, A193675, A326867, A326876, A326878, A326882, A326883.

Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union@@@Tuples[#,2]]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

cp's OEIS Frontend

A102894 Number of ACI algebras or semilattices on n generators, with no identity or annihilator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102895 Number of ACI algebras or semilattices on n generators with no identity element.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A193674 Number of nonisomorphic systems enumerated by A102896; that is, the number of inequivalent closure operators (or Moore families).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A108798 Number of nonisomorphic systems enumerated by A102894; that is, the number of inequivalent closure operators in which the empty set is closed. Also, the number of union-closed sets with n elements that contain the universe and the empty set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A108800 Number of nonisomorphic systems enumerated by A102895.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A326881 Number of set-systems with {} that are closed under intersection and cover n vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326906 Number of sets of subsets of {1..n} that are closed under union and cover all n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326907 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and cover all n vertices. First differences of A193675.

Views