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

%I #49 Mar 21 2024 17:45:49

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

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

%C 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.

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

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

%C 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

%D G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.

%D Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.

%D 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]

%D E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

%H Andrew J. Blumberg, Michael A. Hill, Kyle Ormsby, Angélica M. Osorno, and Constanze Roitzheim, <a href="https://doi.org/10.1090/noti2882">Homotopical Combinatorics</a>, Notices Amer. Math. Soc. (2024) Vol. 71, No. 2, 260-266. See p. 261.

%H Daniel Borchmann and Bernhard Ganter, <a href="https://doi.org/10.1007/978-3-642-01815-2_2">Concept Lattice Orbifolds - First Steps</a>, Proceedings of the 7th International Conference on Formal Concept Analysis (ICFCA 2009), 22-37.

%H Pierre Colomb, Alexis Irlande, Olivier Raynaud and Yoan Renaud, <a href="http://www.colomb.me/pierre/data/paper/icfca2011.pdf">About the Recursive Decomposition of the lattice of co-Moore Families</a>.

%H Pierre Colomb, Alexis Irlande, Olivier Raynaud, and Yoan Renaud, <a href="https://doi.org/10.1007/s10472-013-9362-x">Recursive decomposition tree of a Moore co-family and closure algorithm</a>, Annals of Mathematics and Artificial Intelligence, 2013, DOI 10.1007/s10472-013-9362-x.

%H Nachum Dershowitz, Mitchell A. Harris, and Guan-Shieng Huang, <a href="http://arxiv.org/abs/cs/0610054">Enumeration Problems Related to Ground Horn Theories</a>, arXiv:cs/0610054v2 [cs.LO], 2006-2008.

%H Michel Habib and Lhouari Nourine, <a href="https://doi.org/10.1016/j.disc.2004.11.010">The number of Moore families on n = 6</a>, Discrete Math., 294 (2005), 291-296.

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

%F For asymptotics see A102897.

%F a(n) = A102897(n)/2. - _Gus Wiseman_, Jul 31 2019

%e From _Gus Wiseman_, Jul 31 2019: (Start)

%e The a(0) = 1 through a(2) = 7 set-systems closed under union:

%e {} {} {}

%e {{1}} {{1}}

%e {{2}}

%e {{1,2}}

%e {{1},{1,2}}

%e {{2},{1,2}}

%e {{1},{2},{1,2}}

%e (End)

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

%Y For set-systems closed under union:

%Y - The covering case is A102894.

%Y - The unlabeled case is A193674.

%Y - The case also closed under intersection is A306445.

%Y - Set-systems closed under overlapping union are A326866.

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

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

%K nonn,hard,more

%O 0,2

%A _Mitch Harris_, Jan 18 2005

%E _N. J. A. Sloane_ added a(6) from the Habib et al. reference, May 26 2005

%E Additional comments from _Don Knuth_, Jul 01 2005

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