|
%I M0817 N0309 #297 Nov 30 2023 10:54:42
%S 2,3,6,20,168,7581,7828354,2414682040998,56130437228687557907788,
%T 286386577668298411128469151667598498812366
%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
%C The unlabeled case is A003182. - _Gus Wiseman_, Feb 20 2019
%C From _Amiram Eldar_, May 28 2021 and _Michel Marcus_, Apr 07 2023: (Start)
%C The terms were first calculated by:
%C a(0)-a(4) - Dedekind (1897)
%C a(5) - Church (1940)
%C a(6) - Ward (1946)
%C a(7) - Church (1965, verified by Berman and Kohler, 1976)
%C a(8) - Wiedemann (1991)
%C a(9) - Jäkel (2023)
%C a(9) - independently computed by Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl (2023)
%C (End)
%D Ian Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
%D Jorge Luis Arocha, Antichains in ordered sets [in Spanish], Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico, Vol. 27 (1987), pp. 1-21.
%D Joel Berman and Peter Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124.
%D Garrett Birkhoff, Lattice Theory, American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
%D Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
%D J. D. Farley, Was Gelfand right? The many loves of lattice theory, Notices AMS 69:2 (2022),190-197.
%D Michael A. Harrison, Introduction to Switching and Automata Theory, McGraw Hill, NY, 1965, p. 188.
%D Donald 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, in D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971, pp. 173-181.
%D Saburo Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, pp. 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 Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.
%H Frank a Campo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Campo/campo3.html"> Relations between powers of Dedekind Numbers and exponential sums related to them</a>, J. Int. Seq. Vol. 21 (2018), Article 18.4.4.
%H Frank a Campo, <a href="https://arxiv.org/abs/2206.10293">A Flexible Approach for the Enumeration of Down-Sets and its Application on Dedekind Numbers</a>, arXiv:2206.10293 [math.CO], 2022.
%H Aureli Alabert, Mercè Farré, and Rubén Montes, <a href="https://arxiv.org/abs/2210.13100">Optimal Decision Rules for the Discursive Dilemma</a>, arXiv:2210.13100 [math.OC], 2022.
%H J. M. Aranda, <a href="/A000372/a000372.c.txt">C program</a>
%H Valentin Bakoev, <a href="https://arxiv.org/abs/1902.06110">Combinatorial and Algorithmic Properties of One Matrix Structure at Monotone Boolean Functions</a>, arXiv:1902.06110 [cs.DM], 2019.
%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, Vol. 27, No. 1 (1979), pp. 1-9. MR0541338 (81b:05010)
%H Achille Basile, Anna De Simone, and Ciro Tarantino, <a href="https://doi.org/10.3390/g13060078">A Note on Binary Strategy-Proof Social Choice Functions</a>, Games (2022), Vol. 13, 78.
%H Ringo Baumann and Hannes Strass, <a href="https://doi.org/10.1093/logcom/exx025">On the number of bipolar Boolean functions</a>, Journal of Logic and Computation, Vol. 27, No. 8 (2017), pp. 2431-2449; <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.719.7011&rep=rep1&type=pdf">preprint</a>.
%H Martin Berglund, Brink van der Merwe, and Steyn van Litsenborgh, <a href="https://doi.org/10.3897/jucs.66330">Regular Expressions with Lookahead</a>, J. Universal Comp. Sci. (2021) Vol. 27, No. 4, 324-340.
%H Joel Berman, <a href="https://doi.org/10.1007/BFb0063428">Free spectra of 3-element algebras</a>, in R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math., Vol. 1004, Springer, Berlin, Heidelberg, 1983, pp. 10-53.
%H Joel Berman and Peter Koehler, <a href="/A006356/a006356.pdf">Cardinalities of finite distributive lattices</a>, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124. [Annotated scanned copy]
%H J. Berman and P. Köhler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Koehler/koehler5.html">On Dedekind Numbers and Two Sequences of Knuth</a>, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
%H Stefan 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 Kevin S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>.
%H Kevin S. Brown, <a href="https://www.mathpages.com/home/kmath094/kmath094.htm">Generating the Monotone Boolean Functions</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 Randolph 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 Randolph Church, Enumeration by rank of the free distributive lattice with seven generators, Notices of the American Mathematical Society, Vol. 12, No. 6 (1965), p. 724; <a href="https://www.ams.org/journals/notices/196510/196510FullIssue.pdf">entire volume</a>.
%H Jacob North Clark and Stephen Montgomery-Smith, <a href="https://arxiv.org/abs/1809.07747">Shapley-like values without symmetry</a>, arXiv:1809.07747 [econ.TH], 2018.
%H Gábor Czédli, <a href="https://arxiv.org/abs/2309.13783">Minimum-sized generating sets of the direct powers of free distributive lattices</a>, arXiv:2309.13783 [math.CO], 2023. See p. 16.
%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 and 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 Patrick De Causmaecker, S. De Wannemacker, and 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 Richard Dedekind, <a href="https://doi.org/10.1007/978-3-663-07224-9_1">Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Theiler</a>, Festschrift Hoch. Braunschweig u. ges. Werke(II), 1897, pp. 103-148.; <a href="https://publikationsserver.tu-braunschweig.de/receive/dbbs_mods_00029233">alternative link</a>.
%H Conor Finn and Joseph T. Lizier, <a href="https://arxiv.org/abs/1909.12166">Generalised Measures of Multivariate Information Content</a>, arXiv:1909.12166 [cs.IT], 2019.
%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 E. N. Gilbert, <a href="https://doi.org/10.1002/sapm195433157">Lattice theoretic properties of frontal switching functions</a>, J. Math. Phys., Vol. 33, No. 1-4, (1954), pp. 57-67, see Table III.
%H Milton W. Green, <a href="/A003075/a003075.pdf">Letter to N. J. A. Sloane, 1973</a> (note "A360" refers to N0360 which is A000788).
%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="https://web.archive.org/web/20150911060239/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 Dmitry I. Ignatov, <a href="https://fca4ai.hse.ru/mirror/pubs/share/direct/853774720.pdf#page=47">A Note on Counting Basic Choice Functions with Formal Concept Analysis</a>, 32nd Int'l Joint Conf. on Artif. Int., Formal Conc. Anal. Artif. Int. (IJCAI, FCA4AI 2023) 47-55.
%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 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a000/A000372.java">Java program</a> (github)
%H Christian Jäkel, <a href="https://arxiv.org/abs/2304.00895">A computation of the ninth Dedekind Number</a>, arXiv:2304.00895 [math.CO], 2023.
%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 Jonathan L. King, <a href="http://www.math.ufl.edu/~squash/">Brick tiling and monotone Boolean functions</a> [Dead link, see next link].
%H Jonathan L. King, <a href="https://arxiv.org/abs/math/9809176">A change-of-coordinates from Geometry to Algebra, applied to Brick Tilings</a>, arXiv:math/9809176 [math.CO], 1998.
%H Bjørn Kjos-Hanssen and Lei Liu, <a href="https://math.hawaii.edu/~bjoern/Publications/KH-Liu-TAMC.pdf">The number of languages with maximum state complexity</a>, 2018.
%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 Mathematics 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 Saburo Muroga, 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 Bartlomiej Pawelski, <a href="https://arxiv.org/abs/2108.13997">On the number of inequivalent monotone Boolean functions of 8 variables</a>, arXiv:2108.13997 [math.CO], 2021. See Table 2 p. 2.
%H Bartlomiej Pawelski, <a href="https://arxiv.org/abs/2305.06346">On the number of inequivalent monotone Boolean functions of 9 variables</a>, arXiv:2305.06346 [math.CO], 2023.
%H Bartlomiej Pawelski and Andrzej Szepietowski, <a href="https://arxiv.org/abs/2302.04615">Divisibility properties of Dedekind numbers</a>, arXiv:2302.04615 [math.CO], 2023.
%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 Andrzej Szepietowski, <a href="https://arxiv.org/abs/2205.03868">Fixes of permutations acting on monotone Boolean functions</a>, arXiv:2205.03868 [math.CO], 2022. See p. 17.
%H V. G. Tkachenco and 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 Erdős/Stone Theorem</a>, Sept. 13, 2001.
%H Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl, <a href="https://arxiv.org/abs/2304.03039">A computation of D(9) using FPGA Supercomputing</a>, arXiv:2304.03039 [cs.DM], 2023.
%H Morgan Ward, <a href="https://doi.org/10.1090/S0002-9904-1946-08568-7">Note on the order of free distributive lattices</a> Bulletin of the American Mathematical Society, Vol. 52, No. 5 (1946), p. 423.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DedekindNumber.html">Dedekind Number</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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dedekind_number">Dedekind number</a>.
%H Gus Wiseman, <a href="/A048143/a048143_4.txt">Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons</a>.
%H K. Yamamoto, <a href="https://doi.org/10.2969/jmsj/00630343">Logarithmic order of free distributive lattice</a>, Math. Soc. Japan, 6 (1954), 343-353.
%H R. Zeno, <a href="http://mam2000.mathforum.org/epigone/sci.math/plebrungchoo">A007501 is an upper bound</a> [Dead link]
%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
%F From _J. M. Aranda_, Jun 12 2021: (Start)
%F a(n) = A132581(2^n) = A132581(2^n-2^m) + A132581(2^n-2^(n-m)) for n >= m >= 0.
%F a(n) = A132582(3*2^n -1) for n >= 0.
%F (End)
%e a(2)=6 from the antichains {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
%e From _Gus Wiseman_, Feb 20 2019: (Start)
%e The a(0) = 2 through a(3) = 20 antichains:
%e {} {} {} {}
%e {{}} {{}} {{}} {{}}
%e {{1}} {{1}} {{1}}
%e {{2}} {{2}}
%e {{12}} {{3}}
%e {{1}{2}} {{12}}
%e {{13}}
%e {{23}}
%e {{123}}
%e {{1}{2}}
%e {{1}{3}}
%e {{2}{3}}
%e {{1}{23}}
%e {{2}{13}}
%e {{3}{12}}
%e {{12}{13}}
%e {{12}{23}}
%e {{13}{23}}
%e {{1}{2}{3}}
%e {{12}{13}{23}}
%e (End)
%t nn=5;
%t stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
%t Table[Length[stableSets[Subsets[Range[n]],SubsetQ]],{n,0,nn}] (* _Gus Wiseman_, Feb 20 2019 *)
%t Table[Total[Boole[Table[UnateQ[BooleanFunction[k, n]], {k, 0, 2^(2^n) - 1}]]], {n, 0, 4}] (* _Eric W. Weisstein_, Jun 27 2023 *)
%Y Equals A014466 + 1, also A007153 + 2. Cf. A003182, A059119.
%Y Cf. A006126, A006602, A261005, A293606, A293993, A304996, A305000, A305844, A306505, A317674, A319721, A320449, A321679.
%K nonn,hard,more,nice
%O 0,1
%A _N. J. A. Sloane_
%E a(8) from D. H. Wiedemann, personal communication, Nov 03 1990
%E Additional comments from _Michael Somos_, Jun 10 2002
%E a(9) from C. Jäkel added by _Michel Marcus_, Apr 04 2023
|
