|
|
A102895
|
|
Number of ACI algebras or semilattices on n generators with no identity element.
|
|
22
|
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain the empty set.
|
|
REFERENCES
|
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.
P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010)
E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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.
The a(0) = 1 through a(2) = 8 sets of sets with {} that are closed under intersection are:
{{}} {{}} {{}}
{{},{1}} {{},{1}}
{{},{2}}
{{},{1,2}}
{{},{1},{2}}
{{},{1},{1,2}}
{{},{2},{1,2}}
{{},{1},{2},{1,2}}
(End)
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n]]], MemberQ[#, {}]&&SubsetQ[#, Intersection@@@Tuples[#, 2]]&]], {n, 0, 3}] (* Gus Wiseman, Aug 02 2019 *)
|
|
CROSSREFS
|
The connected case (i.e., with maximum) is A102894.
The same for union instead of intersection is A102896.
The case also closed under union is A326878.
The BII-numbers of these set-systems (without the empty set) are A326880.
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Additional comments from Don Knuth, Jul 01 2005
|
|
STATUS
|
approved
|
|
|
|