A007153 Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786, 286386577668298411128469151667598498812364

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• nice

Comments

Equivalently, the number of elements of the free distributive lattice with n generators.

A monotone Boolean function is an increasing functions from P(S), the set of subsets of S, to {0,1}.

The count of antichains excludes the empty antichain which contains no subsets and the antichain consisting of only the empty set.

The number of continuous functions f : R^n->R with f(x_1,..,x_n) in {x_1,..,x_n}. - Jan Fricke, Feb 12 2004

From Robert FERREOL, Mar 23 2009: (Start)

a(n) is also the number of reduced normal conjunctive forms with n variables without negation.

For example the 18 forms for n=3 are :

a

b

c

a or b

a or c

b or c

a or b or c

a and b

a and c

b and c

a and (b or c)

b and (a or c)

c and (a or b)

(a or b) and (a or c)

(b or a) and (b or c)

(c or a) and (c or b)

a and b and c

(a or b) and (a or c) and (b or c)

(End)

Examples

			a(2)=4 from the antichains {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
		

References

• I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
• J. L. Arocha, (1987) "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21.
• R. Balbes and P. Dwinger, Distributive Lattices, Univ. Missouri Press, 1974, see p. 97. - N. J. A. Sloane, Aug 15 2010
• J. Berman, "Free spectra of 3-element algebras", in R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983.
• G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.
• W. F. Lunnon, The IU function: the size of a free distributive lattice, pp. 173-181 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
• S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

Links

• K. S. Brown, Dedekind's problem
• J. Berman, Free spectra of 3-element algebras, R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983. (Annotated scanned copy)
• Sara Billey and Matjaž Konvalinka, Generalized rank functions and quilts of alternating sign matrices, arXiv:2412.03236 [math.CO], 2024. See pp. 32, 35.
• R. Church, Numerical analysis of certain free distributive lattices, Duke Math. J., 6 (1940), 732-734.
• Jacob North Clark and Stephen Montgomery-Smith, Shapley-like values without symmetry, arXiv:1809.07747 [econ.TH], 2018.
• J. D. Farley, Was Gelfand right? The many loves of lattice theory, Notices AMS 69:2 (2022), 190-197.
• J. L. King, Brick tiling and monotone Boolean functions
• D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 1969 677-682.
• D. J. Kleitman and G. Markowsky, On Dedekind's problem: the number of isotone Boolean functions. II, Trans. Amer. Math. Soc. 213 (1975), 373-390.
• N. M. Rivière, Recursive formulas on free distributive lattices, J. Combin. Theory, 5 (1968), 229-234. - _N. J. A. Sloane_, Aug 15 2010
• N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
• M. Ward, Note on the order of the free distributive lattice, Bull. Amer. Math. Soc., (1946), Abstract 52-5-135 p.423. - _N. J. A. Sloane_, Aug 15 2010
• Eric Weisstein's World of Mathematics, Antichain
• D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991) 5-6.
• K. Yamamoto, Logarithmic order of free distributive lattice, Math. Soc. Japan, 6 (1954), 343-353. - _N. J. A. Sloane_, Aug 15 2010
• Index entries for sequences related to Boolean functions

Crossrefs

Equals A000372 - 2 and A014466 - 1.. Cf. A003182.

Extensions

Last term from D. H. Wiedemann, personal communication

Additional comments from Michael Somos, Jun 10 2002

Term a(9) (using A000372) from Joerg Arndt, Apr 07 2023