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

2, 4, 14, 122, 4960, 2771104, 151947502948, 28175296471414704944

Offset: 0

Author

Mitch Harris, Jan 18 2005

Keywords

• nonn
• hard
• more

Comments

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.

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).

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

Also the number of finite sets of finite subsets of {1..n} that are closed under union. - Gus Wiseman, Aug 03 2019

Examples

			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.
From _Gus Wiseman_, Aug 03 2019: (Start)
The a(0) = 2 through a(2) = 14 sets of subsets closed under union:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{2}}
                  {{1,2}}
                  {{},{1}}
                  {{},{2}}
                  {{},{1,2}}
                  {{1},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{1,2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)
		

References

• V. B. Alekseev, On the number of intersection semilattices [in Russian], Diskretnaya Mat. 1 (1989), 129-136.
• G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
• Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.
• 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.
• P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
• Alfred Horn, Journal of Symbolic Logic 16 (1951), 14-21. [See Lemma 7.]
• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
• E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

Links

• N. Dershowitz, G. S. Huang and M. Harris, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
• D. E. Knuth, HORN-COUNT

Crossrefs

For nonempty set systems of the same type, see A121921.

Regarding sets of subsets closed under union:

- The case with an edge containing all of the vertices is A102895.

- The case without empty edges is A102896.

- The case with intersection instead of union is (also) A102897.

- The unlabeled version is A193675.

- The case closed under both union and intersection is A306445.

- The BII-numbers of set-systems closed under union are A326875.

- The covering case is A326906.

Cf. A102894, A108798, A108800, A193674, A193675, A326866, A326880, A326900.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* Gus Wiseman, Aug 03 2019 *)

Formula

a(n) = 2*A102896(n) = Sum_{k=0..n} C(n, k)*A102895(k), where C(n, k) is the binomial coefficient

Asymptotically, log_2 a(n) ~ binomial(n, floor(n/2)) for all of A102894, A102895, A102896 and this sequence [Alekseev; Burosch et al.]

Extensions

Additional comments from Don Knuth, Jul 01 2005