cp's OEIS Frontend

A102897 Number of ACI algebras (or semilattices) on n generators.

%I A102897 #40 Jan 04 2021 19:57:33
%S A102897 2,4,14,122,4960,2771104,151947502948,28175296471414704944
%N A102897 Number of ACI algebras (or semilattices) on n generators.
%C A102897 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 A102897 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 A102897 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
%C A102897 Also the number of finite sets of finite subsets of {1..n} that are closed under union. - _Gus Wiseman_, Aug 03 2019
%D A102897 V. B. Alekseev, On the number of intersection semilattices [in Russian], Diskretnaya Mat. 1 (1989), 129-136.
%D A102897 G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
%D A102897 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 A102897 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 A102897 P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
%D A102897 Alfred Horn, Journal of Symbolic Logic 16 (1951), 14-21. [See Lemma 7.]
%D A102897 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
%D A102897 E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
%H A102897 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 A102897 D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html">HORN-COUNT</a>
%F A102897 a(n) = 2*A102896(n) = Sum_{k=0..n} C(n, k)*A102895(k), where C(n, k) is the binomial coefficient
%F A102897 Asymptotically, log_2 a(n) ~ binomial(n, floor(n/2)) for all of A102894, A102895, A102896 and this sequence [Alekseev; Burosch et al.]
%e A102897 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 A102897 From _Gus Wiseman_, Aug 03 2019: (Start)
%e A102897 The a(0) = 2 through a(2) = 14 sets of subsets closed under union:
%e A102897   {}    {}        {}
%e A102897   {{}}  {{}}      {{}}
%e A102897         {{1}}     {{1}}
%e A102897         {{},{1}}  {{2}}
%e A102897                   {{1,2}}
%e A102897                   {{},{1}}
%e A102897                   {{},{2}}
%e A102897                   {{},{1,2}}
%e A102897                   {{1},{1,2}}
%e A102897                   {{2},{1,2}}
%e A102897                   {{},{1},{1,2}}
%e A102897                   {{},{2},{1,2}}
%e A102897                   {{1},{2},{1,2}}
%e A102897                   {{},{1},{2},{1,2}}
%e A102897 (End)
%t A102897 Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* _Gus Wiseman_, Aug 03 2019 *)
%Y A102897 For nonempty set systems of the same type, see A121921.
%Y A102897 Regarding sets of subsets closed under union:
%Y A102897 - The case with an edge containing all of the vertices is A102895.
%Y A102897 - The case without empty edges is A102896.
%Y A102897 - The case with intersection instead of union is (also) A102897.
%Y A102897 - The unlabeled version is A193675.
%Y A102897 - The case closed under both union and intersection is A306445.
%Y A102897 - The BII-numbers of set-systems closed under union are A326875.
%Y A102897 - The covering case is A326906.
%Y A102897 Cf. A102894, A108798, A108800, A193674, A193675, A326866, A326880, A326900.
%K A102897 nonn,hard,more
%O A102897 0,1
%A A102897 _Mitch Harris_, Jan 18 2005
%E A102897 Additional comments from _Don Knuth_, Jul 01 2005