%I #40 Jan 04 2021 19:57:33
%S 2,4,14,122,4960,2771104,151947502948,28175296471414704944
%N Number of ACI algebras (or semilattices) on n generators.
%C Also counts Horn functions on n variables, Boolean functions whose set of truth assignments are closed under 'and', or equivalently, the Boolean functions that can be written as a conjunction of Horn clauses, clauses with at most one negative literal.
%C Also, number of families of subsets of {1,...,n} that are closed under intersection (because we can throw in the universe, or take it out, without affecting anything else).
%C An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
%C Also the number of finite sets of finite subsets of {1..n} that are closed under union. - _Gus Wiseman_, Aug 03 2019
%D V. B. Alekseev, On the number of intersection semilattices [in Russian], Diskretnaya Mat. 1 (1989), 129-136.
%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 G. Burosch, J. Demetrovics, G. O. H. Katona, D. J. Kleitman and A. A. Sapozhenko, On the number of closure operations, in Combinatorics, Paul Erdős is Eighty (Volume 1), Keszthely: Bolyai Society Mathematical Studies, 1993, 91-105.
%D P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
%D Alfred Horn, Journal of Symbolic Logic 16 (1951), 14-21. [See Lemma 7.]
%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
%D E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
%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 D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html">HORN-COUNT</a>
%F a(n) = 2*A102896(n) = Sum_{k=0..n} C(n, k)*A102895(k), where C(n, k) is the binomial coefficient
%F Asymptotically, log_2 a(n) ~ binomial(n, floor(n/2)) for all of A102894, A102895, A102896 and this sequence [Alekseev; Burosch et al.]
%e a(2) = 14: Let the points be labeled a, b. We want the number of collections of subsets of {a, b} which are closed under intersection. 0 subsets: 1 way ({}), 1 subset: 4 ways (0; a; b; ab), 2 subsets: 5 ways (0,a; 0,b; 0,ab; a,ab; b,ab) [not a,b because their intersection, 0, would be missing], 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 14.
%e From _Gus Wiseman_, Aug 03 2019: (Start)
%e The a(0) = 2 through a(2) = 14 sets of subsets closed under union:
%e {} {} {}
%e {{}} {{}} {{}}
%e {{1}} {{1}}
%e {{},{1}} {{2}}
%e {{1,2}}
%e {{},{1}}
%e {{},{2}}
%e {{},{1,2}}
%e {{1},{1,2}}
%e {{2},{1,2}}
%e {{},{1},{1,2}}
%e {{},{2},{1,2}}
%e {{1},{2},{1,2}}
%e {{},{1},{2},{1,2}}
%e (End)
%t Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* _Gus Wiseman_, Aug 03 2019 *)
%Y For nonempty set systems of the same type, see A121921.
%Y Regarding sets of subsets closed under union:
%Y - The case with an edge containing all of the vertices is A102895.
%Y - The case without empty edges is A102896.
%Y - The case with intersection instead of union is (also) A102897.
%Y - The unlabeled version is A193675.
%Y - The case closed under both union and intersection is A306445.
%Y - The BII-numbers of set-systems closed under union are A326875.
%Y - The covering case is A326906.
%Y Cf. A102894, A108798, A108800, A193674, A193675, A326866, A326880, A326900.
%K nonn,hard,more
%O 0,1
%A _Mitch Harris_, Jan 18 2005
%E Additional comments from _Don Knuth_, Jul 01 2005
|