%I A000372 M0817 N0309
%S A000372 2,3,6,20,168,7581,7828354,2414682040998,56130437228687557907788
%N A000372 Dedekind numbers: number of monotone Boolean functions of n variables 
               or number of antichains of subsets of an n-set.
%C A000372 A monotone Boolean function is an increasing functions from P(S), the 
               set of subsets of S, to {0,1}.
%C A000372 The count of antichains includes the empty antichain which contains no 
               subsets and the antichain consisting of only the empty set.
%C A000372 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
%C A000372 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
%D A000372 I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, 
               p. 38.
%D A000372 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.
%D A000372 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.
%D A000372 J. Berman and P. Koehler, Cardinalities of finite distributive lattices, 
               Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 
               103-124.
%D A000372 G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium 
               Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
%D A000372 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
%D A000372 E. N. Gilbert, Lattice theoretic properties of frontal switching functions, 
               J. Math. Phys., 33 (1954), 57-67, see Table III.
%D A000372 Sylvain Guilley, Laurent Sauvage, Jean-Luc Danger, Tarik Graba and Yves 
               Mathieu, "Evaluation of Power-Constant Dual-Rail Logic as a Protection 
               of Cryptographic Applications in FPGAs", SSIRI - Secure System Integration 
               and Reliability Improvement, Yokohama: Japan (2008), pp 16-23, DOI: 
               10.1109/SSIRI.2008.31 ; http://hal.archives-ouvertes.fr/hal-00259153/
               en/ [From Sylvain GUILLEY (Sylvain.Guilley(AT)TELECOM-ParisTech.fr), 
               Aug 20 2009]
%D A000372 M. A. Harrison, Introduction to Switching and Automata Theory. McGraw 
               Hill, NY, 1965, p. 188.
%D A000372 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 A000372 D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean 
               functions. Proc. Amer. Math. Soc. 21 1969 677-682.
%D A000372 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.
%D A000372 A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. 
               No. 38, (1981), 5-108, 272. MR0640855 (83h:06013)
%D A000372 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.
%D A000372 S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 
               38 and 214.
%D A000372 R. A. Obando, On the number of nondegenerate monotone boolean functions 
               of n variables in an n-variable boolean algebra. In preparation.
%D A000372 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000372 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000372 D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 
               2001, p. 349.
%D A000372 D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 
               (1991) 5-6.
%H A000372 K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's 
               problem</a>
%H A000372 K. S. Brown, <a href="http://www.mathpages.com/home/kmath094.htm">Asymptotic 
               upper and lower bounds</a>
%H A000372 J. L. King, <a href="http://www.math.ufl.edu/~squash/">Brick tiling and 
               monotone Boolean functions</a>
%H A000372 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Antichain.html">Link to a section of The World of Mathematics.</a>
%H A000372 R. Zeno, <a href="http://mam2000.mathforum.org/epigone/sci.math/plebrungchoo">
               A007501 is an upper bound</a>
%H A000372 <a href="Sindx_Bo.html#Boolean">Index entries for sequences related to 
               Boolean functions</a>
%H A000372 R. A. Obando, <a href="http://www.wolframscience.com/summerschool/2004/
               ">Project: A map of a rule space (to be posted)</a>.
%F A000372 The asymptotics can be found in the Korshunov paper. - Boris Bukh (brbukh(AT)yahoo.com), 
               Nov 07 2003
%F A000372 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
%e A000372 a(2)=6 from the antichains {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
%Y A000372 Equals A014466 + 1, also A007153 + 2. Cf. A003182, A059119.
%Y A000372 Sequence in context: A124066 A093447 A002078 this_sequence A123930 A125601 
               A025239
%Y A000372 Adjacent sequences: A000369 A000370 A000371 this_sequence A000373 A000374 
               A000375
%K A000372 nonn,hard,nice
%O A000372 0,1
%A A000372 N. J. A. Sloane (njas(AT)research.att.com).
%E A000372 Last term from D. H. Wiedemann, personal communication.
%E A000372 Additional comments from Michael Somos, Jun 10 2002.