login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000372 Dedekind numbers or Dedekind's problem: number of monotone Boolean functions of n variables, number of antichains of subsets of an n-set, number of elements in a free distributive lattice on n generators, number of Sperner families.
(Formerly M0817 N0309)
30

%I M0817 N0309

%S 2,3,6,20,168,7581,7828354,2414682040998,56130437228687557907788

%N Dedekind numbers or Dedekind's problem: number of monotone Boolean functions of n variables, number of antichains of subsets of an n-set, number of elements in a free distributive lattice on n generators, number of Sperner families.

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

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

%C 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_, Nov 06 2003

%C Also the number of simple games with n players in minimal winning form. - _Fabián Riquelme_, May 29 2011

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

%D 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 Balbes, Raymond. On counting Sperner families. J. Combin. Theory Ser. A 27 (1979), no. 1, 1--9. MR0541338 (81b:05010) [From _N. J. A. Sloane_, Mar 19 2012]

%D 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 J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.

%D G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.

%D S. Bolus, A QOBDD-based Approach to Simple Games, Dissertation, Doktor der Ingenieurwissenschaften der Technischen Fakultaet der Christian-Albrechts-Universitaet zu Kiel, http://www.informatik.uni-kiel.de/~stb/files/diss_bolus.pdf, 2012. - From _N. J. A. Sloane_, Dec 22 2012

%D Donald E. Campbell, Jack Graver and Jerry S. Kelly, There are more strategy-proof procedures than you think, Mathematical Social Sciences 64 (2012) 263-265. - From _N. J. A. Sloane_, Oct 23 2012

%D Church, Randolph. Numerical analysis of certain free distributive structures. Duke Math. J. 6 (1940). 732--734. MR0002842 (2,120c) [According to Math Reviews, gives a(5) incorrectly as 7579]. - _N. J. A. Sloane_, Mar 19 2012

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.

%D R. Dedekind, Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke(II), 1897, pp. 103-148.

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

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

%D 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 D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean functions. Proc. Amer. Math. Soc. 21 1969 677-682.

%D 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 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.

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

%D 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 S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Tom Trotter, An Application of the Erdos/Stone Theorem, Sept. 13, 2001; http://people.math.gatech.edu/~trotter/slides/newhak.pdf

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

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

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath094.htm">Asymptotic upper and lower bounds</a>

%H Ori DAVIDOV and Shyamal PEDDADA, Order-Restricted Inference for Multivariate Binary Data With Application to Toxicology, Journal of the American Statistical Association, December 1, 2011, 106(496): 1394-1404, doi:<a href="http://dx.doi.org/10.1198/jasa.2011.tm10322">10.1198/jasa.2011.tm10322</a>

%H Patrick De Causmaecker and Stefan De Wannemacker, Partitioning in the space of anti-monotonic functions, arXiv:<a href="http://arxiv.org/abs/1103.2877">1103.2877</a>.

%H Patrick De Causmaecker, Stefan De Wannemacker, <a href="http://arxiv.org/abs/1407.4288">On the number of antichains of sets in a finite universe</a>, arXiv:1407.4288 [math.CO], 2014 (see Table 1).

%H Sylvain Guilley, Laurent Sauvage, Jean-Luc Danger, Tarik Graba, and Yves Mathieu, <a href="http://hal.archives-ouvertes.fr/hal-00259153/en/">"Evaluation of Power-Constant Dual-Rail Logic as a Protection of Cryptographic Applications in FPGAs"</a>, SSIRI - Secure System Integration and Reliability Improvement, Yokohama: Japan (2008), pp 16-23, doi:<a href="http://dx.doi.org/10.1109/SSIRI.2008.31">10.1109/SSIRI.2008.31</a> [From Sylvain GUILLEY (Sylvain.Guilley(AT)TELECOM-ParisTech.fr), Aug 20 2009]

%H J. L. King, <a href="http://www.math.ufl.edu/~squash/">Brick tiling and monotone Boolean functions</a>

%H R. A. Obando, <a href="http://www.wolframscience.com/summerschool/2004/participants/obando.html">Project: A map of a rule space</a>.

%H Tamon Stephen and Timothy Yusun, <a href="http://arxiv.org/abs/1209.4623">Counting inequivalent monotone Boolean functions</a>, arXiv preprint arXiv:1209.4623, 2012

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Antichain.html">Antichain</a>

%H R. Zeno, <a href="http://mam2000.mathforum.org/epigone/sci.math/plebrungchoo">A007501 is an upper bound</a>

%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%F The asymptotics can be found in the Korshunov paper. - _Boris Bukh_, Nov 07 2003

%F a(n) = Sum_{k=1..n} binomial(n,k)*A006126(k) + 2, i.e., this sequence is the inverse binomial transform of A006126, plus 2. E.g. a(3) = 3*1 + 3*2 + 1*9 + 2 = 20. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004

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

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

%K nonn,hard,more,nice

%O 0,1

%A _N. J. A. Sloane_.

%E a(8) from D. H. Wiedemann, personal communication, circa 1990.

%E 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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 21 10:11 EDT 2014. Contains 247025 sequences.