cp's OEIS Frontend

A102895 Number of ACI algebras or semilattices on n generators with no identity element.

%I A102895 #42 Aug 03 2019 07:27:43
%S A102895 1,2,8,90,4542,2747402,151930948472,28175295407840207894
%N A102895 Number of ACI algebras or semilattices on n generators with no identity element.
%C A102895 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
%C A102895 Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain the empty set.
%D A102895 G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
%D A102895 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 A102895 P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
%D A102895 E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
%H A102895 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 A102895 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 A102895 For asymptotics see A102897.
%F A102895 a(n > 0) = 2 * A102894(n).
%e A102895 a(2) = 8: Let the points be labeled a, b and let 0 denote the empty set. We want the number of collections of subsets of {a, b} which are closed under intersection and contain the empty subset. 0 subsets: 0 ways, 1 subset: 1 way (0), 2 subsets: 3 ways (0,a; 0,b; 0,ab), 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 8.
%e A102895 From _Gus Wiseman_, Aug 02 2019: (Start)
%e A102895 The a(0) = 1 through a(2) = 8 sets of sets with {} that are closed under intersection are:
%e A102895   {{}}  {{}}      {{}}
%e A102895         {{},{1}}  {{},{1}}
%e A102895                   {{},{2}}
%e A102895                   {{},{1,2}}
%e A102895                   {{},{1},{2}}
%e A102895                   {{},{1},{1,2}}
%e A102895                   {{},{2},{1,2}}
%e A102895                   {{},{1},{2},{1,2}}
%e A102895 (End)
%t A102895 Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}] (* _Gus Wiseman_, Aug 02 2019 *)
%Y A102895 The connected case (i.e., with maximum) is A102894.
%Y A102895 The same for union instead of intersection is A102896.
%Y A102895 The unlabeled version is A108800.
%Y A102895 The case also closed under union is A326878.
%Y A102895 The BII-numbers of these set-systems (without the empty set) are A326880.
%Y A102895 The covering case is A326881.
%Y A102895 Cf. A000798, A102897, A108798, A193674, A193675, A306445, A326883.
%K A102895 nonn,hard,more
%O A102895 0,2
%A A102895 _Mitch Harris_, Jan 18 2005
%E A102895 Additional comments from _Don Knuth_, Jul 01 2005
%E A102895 Changed a(0) from 2 to 1 by _Gus Wiseman_, Aug 02 2019