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

Author

Mitch Harris, Jan 18 2005

Keywords

• nonn
• hard
• more

Comments

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

Examples

			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)
		

References

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

Links

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

Crossrefs

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.

Programs

Mathematica

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

Formula

Inverse binomial transform of A102896.

For asymptotics see A102897.

Extensions

Additional comments from Don Knuth, Jul 01 2005