The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007153 Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.
(Formerly M3551 N1439)
0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (list; graph; refs; listen; history; text; internal format)



Equivalently, the number of free distributive lattices on n points.

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 (fricke(AT)math.uni-siegen.de), 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 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)



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.

R. Church, Numerical analysis of certain free distributive lattices, Duke Math. J., 6 (1946), 732-734. - N. J. A. Sloane, Aug 15 2010

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. M. Riviere, Recursive formulas on free distributive lattices, J. Combin. Theory, 5 (1968), 229-234. - N. J. A. Sloane, Aug 15 2010

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.


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

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)

Jacob North Clark, Stephen Montgomery-Smith, Shapley-like values without symmetry, arXiv:1809.07747 [econ.TH], 2018.

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. 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


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


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

Sequence in context: A330467 A222766 A302827 * A239839 A156870 A240317

Adjacent sequences:  A007150 A007151 A007152 * A007154 A007155 A007156




N. J. A. Sloane


Last term from D. H. Wiedemann, personal communication

Additional comments from Michael Somos, Jun 10 2002



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 February 24 18:55 EST 2021. Contains 341584 sequences. (Running on oeis4.)