login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102895 Number of ACI algebras or semilattices on n generators with no identity element. 22
1, 2, 8, 90, 4542, 2747402, 151930948472, 28175295407840207894 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..7.

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

M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

FORMULA

For asymptotics see A102897.

a(n > 0) = 2 * A102894(n).

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.

From Gus Wiseman, Aug 02 2019: (Start)

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 unlabeled version is A108800.

The case also closed under union is A326878.

The BII-numbers of these set-systems (without the empty set) are A326880.

The covering case is A326881.

Cf. A000798, A102897, A108798, A193674, A193675, A306445, A326883.

Sequence in context: A319124 A294194 A067964 * A297451 A295773 A319125

Adjacent sequences:  A102892 A102893 A102894 * A102896 A102897 A102898

KEYWORD

nonn,hard,more

AUTHOR

Mitch Harris, Jan 18 2005

EXTENSIONS

Additional comments from Don Knuth, Jul 01 2005

Changed a(0) from 2 to 1 by Gus Wiseman, Aug 02 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 8 17:36 EST 2019. Contains 329865 sequences. (Running on oeis4.)