login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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)
93
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,1
COMMENTS
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, Nov 06 2003
Also the number of simple games with n players in minimal winning form. - Fabián Riquelme, May 29 2011
The unlabeled case is A003182. - Gus Wiseman, Feb 20 2019
From Amiram Eldar, May 28 2021 and Michel Marcus, Apr 07 2023: (Start)
The terms were first calculated by:
a(0)-a(4) - Dedekind (1897)
a(5) - Church (1940)
a(6) - Ward (1946)
a(7) - Church (1965, verified by Berman and Kohler, 1976)
a(8) - Wiedemann (1991)
a(9) - Jäkel (2023)
a(9) - independently computed by Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl (2023)
(End)
REFERENCES
Ian Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
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.
Joel Berman and Peter Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124.
Garrett Birkhoff, Lattice Theory, American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
J. D. Farley, Was Gelfand right? The many loves of lattice theory, Notices AMS 69:2 (2022),190-197.
Michael A. Harrison, Introduction to Switching and Automata Theory, McGraw Hill, NY, 1965, p. 188.
Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
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, in D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971, pp. 173-181.
Saburo Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, pp. 38 and 214.
R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables in an n-variable boolean algebra. In preparation.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.
LINKS
Frank a Campo, Relations between powers of Dedekind Numbers and exponential sums related to them, J. Int. Seq. Vol. 21 (2018), Article 18.4.4.
Aureli Alabert, Mercè Farré, and Rubén Montes, Optimal Decision Rules for the Discursive Dilemma, arXiv:2210.13100 [math.OC], 2022.
J. M. Aranda, C program
Raymond Balbes, On counting Sperner families, J. Combin. Theory Ser. A, Vol. 27, No. 1 (1979), pp. 1-9. MR0541338 (81b:05010)
Achille Basile, Anna De Simone, and Ciro Tarantino, A Note on Binary Strategy-Proof Social Choice Functions, Games (2022), Vol. 13, 78.
Ringo Baumann and Hannes Strass, On the number of bipolar Boolean functions, Journal of Logic and Computation, Vol. 27, No. 8 (2017), pp. 2431-2449; preprint.
Martin Berglund, Brink van der Merwe, and Steyn van Litsenborgh, Regular Expressions with Lookahead, J. Universal Comp. Sci. (2021) Vol. 27, No. 4, 324-340.
Joel 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, Springer, Berlin, Heidelberg, 1983, pp. 10-53.
Joel Berman and Peter Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124. [Annotated scanned copy]
J. Berman and P. Köhler, On Dedekind Numbers and Two Sequences of Knuth, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
Stefan Bolus, A QOBDD-based Approach to Simple Games, Dissertation, Doktor der Ingenieurwissenschaften der Technischen Fakultät der Christian-Albrechts-Universität zu Kiel, 2012. - N. J. A. Sloane, Dec 22 2012
Kevin S. Brown, Dedekind's problem.
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. - N. J. A. Sloane, Oct 23 2012
Randolph Church, 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]
Randolph Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940). 732--734. [Scanned annotated copy]
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; entire volume.
Jacob North Clark and Stephen Montgomery-Smith, Shapley-like values without symmetry, arXiv:1809.07747 [econ.TH], 2018.
Gábor Czédli, Minimum-sized generating sets of the direct powers of free distributive lattices, arXiv:2309.13783 [math.CO], 2023. See p. 16.
Ori Davidov and Shyamal Peddada, Order-Restricted Inference for Multivariate Binary Data With Application to Toxicology, Journal of the American Statistical Association, Dec 01 2011, 106(496): 1394-1404, doi:10.1198/jasa.2011.tm10322.
Patrick De Causmaecker and Stefan De Wannemacker, Partitioning in the space of anti-monotonic functions, arXiv:1103.2877 [math.NT], 2011.
Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014 (see Table 1).
Patrick De Causmaecker, S. De Wannemacker, and J. Yellen, Intervals of Antichains and Their Decompositions, arXiv preprint arXiv:1602.04675 [math.CO], 2016.
Richard Dedekind, Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Theiler, Festschrift Hoch. Braunschweig u. ges. Werke(II), 1897, pp. 103-148.; alternative link.
Conor Finn and Joseph T. Lizier, Generalised Measures of Multivariate Information Content, arXiv:1909.12166 [cs.IT], 2019.
Christian Gießen, Monotone Functions on Bitstrings - Some Structural Notes, Theory of Randomized Optimization Heuristics, Dagstuhl Seminar 17191 (2017), 3.12, p. 33.
E. N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys., Vol. 33, No. 1-4, (1954), pp. 57-67, see Table III.
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is A000788).
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
Dmitry I. Ignatov, A Note on Counting Basic Choice Functions with Formal Concept Analysis, 32nd Int'l Joint Conf. on Artif. Int., Formal Conc. Anal. Artif. Int. (IJCAI, FCA4AI 2023) 47-55.
Liviu Ilinca, and Jeff Kahn, Counting maximal antichains and independent sets, arXiv:1202.4427 [math.CO], 2012; Order 30.2 (2013): 427-435.
Sean A. Irvine, Java program (github)
Christian Jäkel, A computation of the ninth Dedekind Number, arXiv:2304.00895 [math.CO], 2023.
J. Kahn, Entropy, independent sets and antichains: a new approach to Dedekind's problem, Proc. Amer. Math. Soc. 130 (2002), no. 2, 371-378.
Jonathan L. King, Brick tiling and monotone Boolean functions [Dead link, see next link].
Jonathan L. King, A change-of-coordinates from Geometry to Algebra, applied to Brick Tilings, arXiv:math/9809176 [math.CO], 1998.
Bjørn Kjos-Hanssen and Lei Liu, The number of languages with maximum state complexity, 2018.
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.
M. M. Krieger, Letter to N. J. A. Sloane, Jul 31 1975, confirming that a(7) = 2414682040998, using W. F. Lunnon's method but getting a different answer.
Mathematics Stack Exchange, Counting antichains in the limit n->oo, 2014.
Saburo Muroga, Iwao Toda, and Satoru Takasu, Theory of majority decision elements, Journal of the Franklin Institute 271.5 (1961): 376-418. [Annotated scans of pages 413 and 414 only]
Bartlomiej Pawelski, On the number of inequivalent monotone Boolean functions of 8 variables, arXiv:2108.13997 [math.CO], 2021. See Table 2 p. 2.
Bartlomiej Pawelski, On the number of inequivalent monotone Boolean functions of 9 variables, arXiv:2305.06346 [math.CO], 2023.
Bartlomiej Pawelski and Andrzej Szepietowski, Divisibility properties of Dedekind numbers, arXiv:2302.04615 [math.CO], 2023.
Tamon Stephen and Timothy Yusun, Counting inequivalent monotone Boolean functions, arXiv preprint arXiv:1209.4623 [cs.DS], 2012.
Andrzej Szepietowski, Fixes of permutations acting on monotone Boolean functions, arXiv:2205.03868 [math.CO], 2022. See p. 17.
V. G. Tkachenco and O. V. Sinyavsky, Blocks of Monotone Boolean Functions of Rank 5, Computer Science and Information Technology 4(4): 139-146, 2016; DOI: 10.13189/csit.2016.040402.
Tom Trotter, An Application of the Erdős/Stone Theorem, Sept. 13, 2001.
Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl, A computation of D(9) using FPGA Supercomputing, arXiv:2304.03039 [cs.DM], 2023.
Morgan Ward, Note on the order of free distributive lattices Bulletin of the American Mathematical Society, Vol. 52, No. 5 (1946), p. 423.
Eric Weisstein's World of Mathematics, Dedekind Number
D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991) 5-6.
Wikipedia, Dedekind number.
K. Yamamoto, Logarithmic order of free distributive lattice, Math. Soc. Japan, 6 (1954), 343-353.
R. Zeno, A007501 is an upper bound [Dead link]
V. D. Zolotarev, Enumeration of Boolean functions (Russian), Izvest. Vyssh. Uchebnykh Zavedenii Elektro. Novocherkassk, #3, 1970, 309-313; Math. Rev., 45#83, Jan. 1973.
FORMULA
The asymptotics can be found in the Korshunov paper. - Boris Bukh, Nov 07 2003
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
From J. M. Aranda, Jun 12 2021: (Start)
a(n) = A132581(2^n) = A132581(2^n-2^m) + A132581(2^n-2^(n-m)) for n >= m >= 0.
a(n) = A132582(3*2^n -1) for n >= 0.
(End)
EXAMPLE
a(2)=6 from the antichains {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
From Gus Wiseman, Feb 20 2019: (Start)
The a(0) = 2 through a(3) = 20 antichains:
{} {} {} {}
{{}} {{}} {{}} {{}}
{{1}} {{1}} {{1}}
{{2}} {{2}}
{{12}} {{3}}
{{1}{2}} {{12}}
{{13}}
{{23}}
{{123}}
{{1}{2}}
{{1}{3}}
{{2}{3}}
{{1}{23}}
{{2}{13}}
{{3}{12}}
{{12}{13}}
{{12}{23}}
{{13}{23}}
{{1}{2}{3}}
{{12}{13}{23}}
(End)
MATHEMATICA
nn=5;
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]]]];
Table[Length[stableSets[Subsets[Range[n]], SubsetQ]], {n, 0, nn}] (* Gus Wiseman, Feb 20 2019 *)
Table[Total[Boole[Table[UnateQ[BooleanFunction[k, n]], {k, 0, 2^(2^n) - 1}]]], {n, 0, 4}] (* Eric W. Weisstein, Jun 27 2023 *)
CROSSREFS
Equals A014466 + 1, also A007153 + 2. Cf. A003182, A059119.
Sequence in context: A361648 A277876 A002078 * A333445 A123930 A238895
KEYWORD
nonn,hard,more,nice
AUTHOR
EXTENSIONS
a(8) from D. H. Wiedemann, personal communication, Nov 03 1990
Additional comments from Michael Somos, Jun 10 2002
a(9) from C. Jäkel added by Michel Marcus, Apr 04 2023
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:59 EDT 2024. Contains 371268 sequences. (Running on oeis4.)