0,1

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

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

a(n) is also equal to the number of upsets of an n-set S. A set U of subsets of S is an upset if whenever A is in U and B is a superset of A then B is in U. - W. Edwin Clark (eclark(AT)math.usf.edu), Nov 06 2003

Also the inverse binomial transform of A006126 with a 2 prepended to the sequence. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004

I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.

J. L. Arocha, Antichains in ordered sets [in Spanish], Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico, 27 (1987), 1-21.

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.

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.

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.

E. N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys., 33 (1954), 57-67, see Table III.

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.

J. Kahn, Entropy, independent sets and antichains, Entropy, independent sets and antichains: a new approach to Dedekind's problem, Proc. Amer. Math. Soc. 130 (2002), no. 2, 371-378.

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.

A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. No. 38, (1981), 5-108, 272. MR0640855 (83h:06013)

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.

D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991) 5-6.

R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables in an n-variable boolean algebra. In preparation.

K. S. Brown, Dedekind's problem

K. S. Brown, Asymptotic upper and lower bounds

J. L. King, Brick tiling and monotone Boolean functions

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

R. Zeno, A007501 is an upper bound

Index entries for sequences related to Boolean functions

R. A. Obando, Project: A map of a rule space (to be posted).

The asymptotics can be found in the Korshunov paper. - Boris Bukh (brbukh(AT)yahoo.com), Nov 07 2003

a(n) = Sum_{k=1..n}C(n, k)*b(k) + 2, where b(k) is the number of antichain covers of a labeled n-set A006126. E.g. a(3) = 3*1 + 3*2 + 1*9 + 2 = 20 - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004

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

Equals A014466 + 1, also A007153 + 2. Cf. A003182, A059119.

Sequence in context: A124066 A093447 A002078 this_sequence A123930 A125601 A025239

Adjacent sequences: A000369 A000370 A000371 this_sequence A000373 A000374 A000375

nonn,hard,nice

njas

Last term from D. H. Wiedemann, personal communication.

Additional comments from Michael Somos, Jun 10 2002.