|
%I #66 Dec 19 2023 13:40:47
%S 1,1,4,45,2271,1373701,75965474236,14087647703920103947
%N Number of ACI algebras or semilattices on n generators, with no identity or annihilator.
%C Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain both the universe and the empty set.
%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 covering n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - _Gus Wiseman_, Aug 01 2019
%C 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
%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 E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
%H Maria Paola Bonacina and Nachum Dershowitz, <a href="https://doi.org/10.1007/978-3-642-37651-1_3">Canonical ground Horn theories</a>, Lecture Notes in Computer Science 7797, 35-71 (2013).
%H P. Colomb, A. Irlande and O. Raynaud, <a href="http://pierre.colomb.me/data/paper/icfca2010.pdf">Counting of Moore Families for n=7</a>, International Conference on Formal Concept Analysis (2010).
%H N. Dershowitz, G. S. Huang and M. Harris, <a href="http://arxiv.org/abs/cs/0610054">Enumeration Problems Related to Ground Horn Theories</a>, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
%H Christopher S. Flippen, <a href="https://scholarscompass.vcu.edu/etd/7527/">Minimal Sets, Union-Closed Families, and Frankl's Conjecture</a>, Master's thesis, Virginia Commonwealth Univ., 2023.
%H M. Habib and L. 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 Inverse binomial transform of A102896.
%F For asymptotics see A102897.
%e From _Gus Wiseman_, Aug 01 2019: (Start)
%e 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.
%e 0 {1} {1}{2} {1}{2}{3} {1}{2}{3}{12} {1}{2}{3}{12}{13}
%e {2} {1}{3} {1}{2}{12} {1}{2}{3}{13} {1}{2}{3}{12}{23}
%e {3} {2}{3} {1}{2}{13} {1}{2}{3}{23} {1}{2}{3}{13}{23}
%e {12} {1}{12} {1}{2}{23} {1}{2}{12}{13}
%e {13} {1}{13} {1}{3}{12} {1}{2}{12}{23}
%e {23} {1}{23} {1}{3}{13} {1}{3}{12}{13} {1}{2}{3}{12}{13}{23}
%e {2}{12} {1}{3}{23} {1}{3}{13}{23}
%e {2}{13} {2}{3}{12} {2}{3}{12}{23}
%e {2}{23} {2}{3}{13} {2}{3}{13}{23}
%e {3}{12} {2}{3}{23}
%e {3}{13} {1}{12}{13}
%e {3}{23} {2}{12}{23}
%e {3}{13}{23}
%e (End)
%t Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* _Gus Wiseman_, Aug 01 2019 *)
%Y Regarding set-systems covering n vertices closed under union:
%Y - The non-covering case is A102896.
%Y - The BII-numbers of these set-systems are A326875.
%Y - The case with intersection instead of union is A326881.
%Y - The unlabeled case is A108798.
%Y Cf. A003465, A072447, A102895, A102897, A108800, A193674, A193675, A306445, A326870, A326880, A326883.
%K nonn,hard,more
%O 0,3
%A _Mitch Harris_, Jan 18 2005
%E Additional comments from _Don Knuth_, Jul 01 2005
| 