OFFSET
0,2
COMMENTS
Or, number of Moore families on an n-set, that is, families of subsets that contain the universal set {1,...,n} and are closed under intersection.
Or, number of closure operators on a set of n elements.
An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
Also the number of set-systems on n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - Gus Wiseman, Jul 31 2019
From Bernhard Ganter, Jul 08 2025: (Start)
Also the number of union-free families of subsets of an n-set; i.e., families of nonempty sets on n elements such that no set is a union of some others.
Also the number of intersection-free families of subsets of an n-set; i.e., of families of proper subsets on n elements such that no set is an intersection of some others.
(Note that every union-free family on an n-set is the set of union-irreducible elements of exactly one union-closed family, and each family of union-irreducible elements is union-free. Same for intersection.) (End)
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). [From Pierre Colomb (pierre(AT)colomb.me), Sep 04 2010]
E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.
LINKS
Andrew J. Blumberg, Michael A. Hill, Kyle Ormsby, Angélica M. Osorno, and Constanze Roitzheim, Homotopical Combinatorics, Notices Amer. Math. Soc. (2024) Vol. 71, No. 2, 260-266. See p. 261.
Daniel Borchmann and Bernhard Ganter, Concept Lattice Orbifolds - First Steps, Proceedings of the 7th International Conference on Formal Concept Analysis (ICFCA 2009), 22-37.
Jishnu Bose, Tien Chih, Hannah Housden, Legrand Jones II, Chloe Lewis, Kyle Ormsby, and Millie Rose, Combinatorics of factorization systems on lattices, arXiv:2503.22883 [math.CO], 2025. See p. 11.
Pierre Colomb, Alexis Irlande, Olivier Raynaud and Yoan Renaud, About the Recursive Decomposition of the lattice of co-Moore Families, ICFCA 2011.
Pierre Colomb, Alexis Irlande, Olivier Raynaud, and Yoan Renaud, Recursive decomposition tree of a Moore co-family and closure algorithm, Annals of Mathematics and Artificial Intelligence, 2013, DOI 10.1007/s10472-013-9362-x.
Nachum Dershowitz, Mitchell A. Harris, and Guan-Shieng Huang, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
Michel Habib and Lhouari Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.
Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young, and Saron Zhu, Enumerating submonoids of finite commutative monoids, arXiv:2508.20786 [math.CO], 2025. See p. 16.
Andrew Salch and Gunjeet Singh, Notes on model structures on preorders, Wayne State Univ. (2025). See p. 30.
FORMULA
a(n) = Sum_{k=0..n} C(n, k)*A102894(k), where C(n, k) is the binomial coefficient.
For asymptotics see A102897.
a(n) = A102897(n)/2. - Gus Wiseman, Jul 31 2019
EXAMPLE
From Gus Wiseman, Jul 31 2019: (Start)
The a(0) = 1 through a(2) = 7 set-systems closed under union:
{} {} {}
{{1}} {{1}}
{{2}}
{{1,2}}
{{1},{1,2}}
{{2},{1,2}}
{{1},{2},{1,2}}
(End)
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], SubsetQ[#, Union@@@Tuples[#, 2]]&]], {n, 0, 3}] (* Gus Wiseman, Jul 31 2019 *)
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Mitch Harris, Jan 18 2005
EXTENSIONS
N. J. A. Sloane added a(6) from the Habib et al. reference, May 26 2005
Additional comments from Don Knuth, Jul 01 2005
a(7) from Pierre Colomb (pierre(AT)colomb.me), Sep 04 2010
STATUS
approved
