%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