A003182 Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.

2, 3, 5, 10, 30, 210, 16353, 490013148, 1392195548889993358, 789204635842035040527740846300252680

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• nice
• more

Comments

NP-equivalence classes of unate Boolean functions of n or fewer variables.

Also the number of simple games with n players in minimal winning form up to isomorphism. - Fabián Riquelme, Mar 13 2018

The labeled case is A000372. - Gus Wiseman, Feb 23 2019

First differs from A348260(n + 1) at a(5) = 210, A348260(6) = 233. - Gus Wiseman, Nov 28 2021

Pawelski & Szepietowski show that a(n) = A001206(n) (mod 2) and that a(9) = 6 (mod 210). - Charles R Greathouse IV, Feb 16 2023

Examples

			From _Gus Wiseman_, Feb 20 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(3) = 10 antichains:
  {}    {}     {}         {}
  {{}}  {{}}   {{}}       {{}}
        {{1}}  {{1}}      {{1}}
               {{1,2}}    {{1,2}}
               {{1},{2}}  {{1},{2}}
                          {{1,2,3}}
                          {{1},{2,3}}
                          {{1},{2},{3}}
                          {{1,3},{2,3}}
                          {{1,2},{1,3},{2,3}}
(End)
		

References

• I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
• Arocha, Jorge Luis (1987) "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21.
• 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.
• G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.
• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
• 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.
• Saburo Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 13.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• D. H. Wiedemann, personal communication.

Links

• K. S. Brown, Dedekind's problem
• Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See pp. 2, 14.
• Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.
• Patrick De Causmaecker and Lennart Van Hirtum, Solving systems of equations on antichains for the computation of the ninth Dedekind Number, arXiv:2405.20904 [math.CO], 2024. See p. 4.
• Liviu Ilinca and Jeff Kahn, Counting maximal antichains and independent sets, arXiv:1202.4427 [math.CO], 2012; Order 30.2 (2013): 427-435.
• J. L. King, Brick tiling and monotone Boolean functions
• 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.
• Sascha Kurz, Competitive learning of monotone Boolean functions, arXiv:1401.8135 [cs.DS], 2014.
• C. L. Mallows, Emails to N. J. A. Sloane, Jun-Jul 1991
• Mikaël Monet and Dan Olteanu, Towards Deterministic Decomposable Circuits for Safe Queries, 2018.
• S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
• 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.
• Bartłomiej Pawelski, Counting and generating monotone Boolean functions, Doctoral Diss., Univ. Gdańsk, (Poland, 2024). See pp. 12, 24, 34-35, 40, 49-50.
• 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, Discrete Applied Mathematics, 167 (2014), 15-24.
• 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.
• Eric Weisstein's World of Mathematics, Boolean Function.
• Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.
• Index entries for sequences related to Boolean functions

Crossrefs

Cf. A000372, A007153, A006602, A007411.

Cf. A006126, A014466, A261005, A293606, A293993, A304996, A305000, A305857, A306505, A319721, A320449, A321679.

Cf. A007363, A046165, A306007, A307249, A326358, A326363.

Formula

a(n) = A306505(n) + 1. - Gus Wiseman, Jul 02 2019

Extensions

a(7) added by Timothy Yusun, Sep 27 2012

a(8) from Pawelski added by Michel Marcus, Sep 01 2021

a(9) from Pawelski added by Michel Marcus, May 11 2023