A102896 Number of ACI algebras (or semilattices) on n generators with no annihilator.

1, 2, 7, 61, 2480, 1385552, 75973751474, 14087648235707352472

Offset: 0

Author

Mitch Harris, Jan 18 2005

Keywords

• nonn
• hard
• more

Comments

Or, number of Moore families on an n-set, that is, families of subsets that contain the universal set {1,...,n} and are closed under intersection.

Or, number of closure operators on a set of n elements.

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

Also the number of set-systems on n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - Gus Wiseman, Jul 31 2019

From Bernhard Ganter, Jul 08 2025: (Start)

Also the number of union-free families of subsets of an n-set; i.e., families of nonempty sets on n elements such that no set is a union of some others.

Also the number of intersection-free families of subsets of an n-set; i.e., of families of proper subsets on n elements such that no set is an intersection of some others.

(Note that every union-free family on an n-set is the set of union-irreducible elements of exactly one union-closed family, and each family of union-irreducible elements is union-free. Same for intersection.) (End)

Examples

			From _Gus Wiseman_, Jul 31 2019: (Start)
The a(0) = 1 through a(2) = 7 set-systems closed under union:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}
(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.
• P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010). [From Pierre Colomb (pierre(AT)colomb.me), Sep 04 2010]
• E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

Links

• Andrew J. Blumberg, Michael A. Hill, Kyle Ormsby, Angélica M. Osorno, and Constanze Roitzheim, Homotopical Combinatorics, Notices Amer. Math. Soc. (2024) Vol. 71, No. 2, 260-266. See p. 261.
• Daniel Borchmann and Bernhard Ganter, Concept Lattice Orbifolds - First Steps, Proceedings of the 7th International Conference on Formal Concept Analysis (ICFCA 2009), 22-37.
• Jishnu Bose, Tien Chih, Hannah Housden, Legrand Jones II, Chloe Lewis, Kyle Ormsby, and Millie Rose, Combinatorics of factorization systems on lattices, arXiv:2503.22883 [math.CO], 2025. See p. 11.
• Pierre Colomb, Alexis Irlande, Olivier Raynaud and Yoan Renaud, About the Recursive Decomposition of the lattice of co-Moore Families, ICFCA 2011.
• Pierre Colomb, Alexis Irlande, Olivier Raynaud, and Yoan Renaud, Recursive decomposition tree of a Moore co-family and closure algorithm, Annals of Mathematics and Artificial Intelligence, 2013, DOI 10.1007/s10472-013-9362-x.
• Nachum Dershowitz, Mitchell A. Harris, and Guan-Shieng Huang, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
• Michel Habib and Lhouari Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

Crossrefs

For set-systems closed under union:

- The covering case is A102894.

- The unlabeled case is A193674.

- The case also closed under intersection is A306445.

- Set-systems closed under overlapping union are A326866.

- The BII-numbers of these set-systems are given by A326875.

Cf. A102895, A102897, A108798, A108800, A193675, A000798, A014466, A326878, A326880, A326881.

Programs

Mathematica

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

Formula

a(n) = Sum_{k=0..n} C(n, k)*A102894(k), where C(n, k) is the binomial coefficient.

For asymptotics see A102897.

a(n) = A102897(n)/2. - Gus Wiseman, Jul 31 2019

Extensions

N. J. A. Sloane added a(6) from the Habib et al. reference, May 26 2005

Additional comments from Don Knuth, Jul 01 2005

a(7) from Pierre Colomb (pierre(AT)colomb.me), Sep 04 2010