This site is supported by donations to The OEIS Foundation.



(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)

%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 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 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 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 Terry Speed, Letter to N. J. A. Sloane, Sep 20 1981.

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

%H Raymond Balbes, <a href="http://dx.doi.org/10.1016/0097-3165(79)90002-5">On counting Sperner families</a>, J. Combin. Theory Ser. A 27 (1979), no. 1, 1--9. MR0541338 (81b:05010)

%H R. Baumann and H. Strass, <a href="http://www.informatik.uni-leipzig.de/~baumann/papers/bipolar.pdf ">On the number of bipolar Boolean functions</a>, to appear (2014).

%H J. Berman and P. Koehler, <a href="/A006356/a006356.pdf">Cardinalities of finite distributive lattices</a>, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]

%H S. Bolus, <a href="http://macau.uni-kiel.de/receive/dissertation_diss_00009114">A QOBDD-based Approach to Simple Games</a>, Dissertation, Doktor der Ingenieurwissenschaften der Technischen Fakultät der Christian-Albrechts-Universität zu Kiel, 2012. - _N. J. A. Sloane_, Dec 22 2012

%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 Donald E. Campbell, Jack Graver and Jerry S. Kelly, <a href="https://doi.org/10.1016/j.mathsocsci.2012.05.001">There are more strategy-proof procedures than you think</a>, Mathematical Social Sciences 64 (2012) 263-265. - _N. J. A. Sloane_, Oct 23 2012

%H Randolph Church, <a href="https://doi.org/10.1215/S0012-7094-40-00655-X">Numerical analysis of certain free distributive structures</a>, 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]

%H R. Church, <a href="/A000372/a000372_3.pdf">Numerical analysis of certain free distributive structures</a>, Duke Math. J. 6 (1940). 732--734. [Scanned annotated copy]

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

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

%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 P. De Causmaecker, S. De Wannemacker, J. Yellen, <a href="https://arxiv.org/abs/1602.04675">Intervals of Antichains and Their Decompositions</a>, arXiv preprint arXiv:1602.04675 [math.CO], 2016.

%H Christian Gießen, <a href="http://drops.dagstuhl.de/opus/volltexte/2017/8279/pdf/dagrep_v007_i005_p022_17191.pdf#page=12">Monotone Functions on Bitstrings - Some Structural Notes</a>, Theory of Randomized Optimization Heuristics, Dagstuhl Seminar 17191 (2017), 3.12, p. 33.

%H Milton W. Green, <a href="/A003075/a003075.pdf">Letter to N. J. A. Sloane, 1973</a>.

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

%H Pieter-Jan Hoedt, <a href="http://people.cs.kuleuven.be/~bart.demoen/WVKULAK/firstdraftofPaper_Hoedt.pdf">Parallelizing with MPI in Java to Find the ninth Dedekind Number</a>, preprint, 2015.

%H Liviu Ilinca, and Jeff Kahn, <a href="https://arxiv.org/abs/1202.4427">Counting maximal antichains and independent sets</a>, arXiv:1202.4427 [math.CO], 2012; Order 30.2 (2013): 427-435.

%H J. Kahn, <a href="http://dx.doi.org/10.1090/S0002-9939-01-06058-0">Entropy, independent sets and antichains: a new approach to Dedekind's problem</a>, Proc. Amer. Math. Soc. 130 (2002), no. 2, 371-378.

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

%H D. J. Kleitman, <a href="http://dx.doi.org/10.1090/S0002-9939-1969-0241334-6">On Dedekind's problem: The number of monotone Boolean functions</a>, Proc. Amer. Math. Soc. 21 1969 677-682.

%H D. J. Kleitman and G. Markowsky, <a href="http://dx.doi.org/10.1090/S0002-9947-1975-0382107-0">On Dedekind's problem: the number of isotone Boolean functions. II</a>, Trans. Amer. Math. Soc. 213 (1975), 373-390.

%H M. M. Krieger, <a href="/A000372/a000372_1.pdf">Letter to N. J. A. Sloane, Jul 31 1975</a>, confirming that a(7) = 2414682040998, using W. F. Lunnon's method but getting a different answer.

%H C. L. Mallows, <a href="/A000372/a000372_5.pdf">Emails to N. J. A. Sloane, Jun-Jul 1991</a>

%H Math. Stack Exchange, <a href="https://math.stackexchange.com/questions/904091/counting-antichains-in-the-limit-n-rightarrow-infty/904164#904164">Counting antichains in the limit n->oo</a>, 2014.

%H Muroga, Saburo, Iwao Toda, and Satoru Takasu, <a href="/A002079/a002079.pdf">Theory of majority decision elements</a>, Journal of the Franklin Institute 271.5 (1961): 376-418. [Annotated scans of pages 413 and 414 only]

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

%H Terry Speed, <a href="/A000372/a000372_4.pdf">Letter to N. J. A. Sloane, Sep 20 1981</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 [cs.DS], 2012.

%H V. G. Tkachenco, O. V. Sinyavsky, <a href="https://doi.org/10.13189/csit.2016.040402">Blocks of Monotone Boolean Functions of Rank 5</a>, Computer Science and Information Technology 4(4): 139-146, 2016; DOI: 10.13189/csit.2016.040402.

%H Tom Trotter, <a href="http://people.math.gatech.edu/~trotter/slides/newhak.pdf">An Application of the Erdos/Stone Theorem</a>, Sept. 13, 2001.

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

%H D. H. Wiedemann, <a href="/A000372/a000372.pdf">Letter to N. J. A. Sloane, Nov 03, 1990</a>

%H D. H. Wiedemann, <a href="https://doi.org/10.1007/BF00385808">A computation of the eighth Dedekind number</a>, Order 8 (1991) 5-6.

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

%H V. D. Zolotarev, <a href="/A000372/a000372_2.pdf">Enumeration of Boolean functions (Russian)</a>, Izvest. Vyssh. Uchebnykh Zavedenii Elektro. Novocherkassk, #3, 1970, 309-313; Math. Rev., 45#83, Jan. 1973.

%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,changed

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

License Agreements, Terms of Use, Privacy Policy .

Last modified April 20 04:17 EDT 2018. Contains 302772 sequences. (Running on oeis4.)