login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102894 Number of ACI algebras or semilattices on n generators, with no identity or annihilator. 22
1, 1, 4, 45, 2271, 1373701, 75965474236, 14087647703920103947 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain both the universe and the empty set.

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

Also the number of set-systems covering n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - Gus Wiseman, Aug 01 2019

Number of strict closure operators on a set of n elements, where the closure operator is said to be strict if the empty set is closed. - Tian Vlasic, Jul 30 2022

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.

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.

Maria Paola Bonacina and Nachum Dershowitz, Canonical ground Horn theories, Lecture Notes in Computer Science 7797, 35-71 (2013).

P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010).

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

Inverse binomial transform of A102896.

For asymptotics see A102897.

EXAMPLE

From Gus Wiseman, Aug 01 2019: (Start)

The a(3) = 45 set-systems with {} and {1,2,3} that are closed under intersection are the following ({} and {1,2,3} not shown). The BII-numbers of these set-systems are given by A326880.

0 {1} {1}{2} {1}{2}{3} {1}{2}{3}{12} {1}{2}{3}{12}{13}

{2} {1}{3} {1}{2}{12} {1}{2}{3}{13} {1}{2}{3}{12}{23}

{3} {2}{3} {1}{2}{13} {1}{2}{3}{23} {1}{2}{3}{13}{23}

{12} {1}{12} {1}{2}{23} {1}{2}{12}{13}

{13} {1}{13} {1}{3}{12} {1}{2}{12}{23}

{23} {1}{23} {1}{3}{13} {1}{3}{12}{13} {1}{2}{3}{12}{13}{23}

{2}{12} {1}{3}{23} {1}{3}{13}{23}

{2}{13} {2}{3}{12} {2}{3}{12}{23}

{2}{23} {2}{3}{13} {2}{3}{13}{23}

{3}{12} {2}{3}{23}

{3}{13} {1}{12}{13}

{3}{23} {2}{12}{23}

{3}{13}{23}

(End)

MATHEMATICA

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

CROSSREFS

Regarding set-systems covering n vertices closed under union:

- The non-covering case is A102896.

- The BII-numbers of these set-systems are A326875.

- The case with intersection instead of union is A326881.

- The unlabeled case is A108798.

Cf. A003465, A072447, A102895, A102897, A108800, A193674, A193675, A306445, A326870, A326880, A326883.

Sequence in context: A132873 A244753 A335014 * A132552 A189273 A288554

Adjacent sequences: A102891 A102892 A102893 * A102895 A102896 A102897

KEYWORD

nonn,hard,more

AUTHOR

Mitch Harris, Jan 18 2005

EXTENSIONS

Additional comments from Don Knuth, Jul 01 2005

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 05:41 EST 2022. Contains 358649 sequences. (Running on oeis4.)