|
%I M0729 #102 May 11 2023 01:44:23
%S 2,3,5,10,30,210,16353,490013148,1392195548889993358,
%T 789204635842035040527740846300252680
%N Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.
%C NP-equivalence classes of unate Boolean functions of n or fewer variables.
%C Also the number of simple games with n players in minimal winning form up to isomorphism. - _Fabián Riquelme_, Mar 13 2018
%C The labeled case is A000372. - _Gus Wiseman_, Feb 23 2019
%C First differs from A348260(n + 1) at a(5) = 210, A348260(6) = 233. - _Gus Wiseman_, Nov 28 2021
%C Pawelski & Szepietowski show that a(n) = A001206(n) (mod 2) and that a(9) = 6 (mod 210). - _Charles R Greathouse IV_, Feb 16 2023
%D I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
%D 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.
%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 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 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 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, Table 2.3.2. - Row 13.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D D. H. Wiedemann, personal communication.
%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>
%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.
%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. 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 S. Kurz, <a href="https://arxiv.org/abs/1401.8135">Competitive learning of monotone Boolean functions</a>, arXiv:1401.8135 [cs.DS], 2014.
%H C. L. Mallows, <a href="/A000372/a000372_5.pdf">Emails to N. J. A. Sloane, Jun-Jul 1991</a>
%H Mikaël Monet and Dan Olteanu, <a href="https://www.cs.ox.ac.uk/people/dan.olteanu/papers/mo-amw18.pdf">Towards Deterministic Decomposable Circuits for Safe Queries</a>, 2018.
%H S. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971 [Annotated scans of a few pages]
%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 Tamon Stephen and Timothy Yusun, <a href="https://doi.org/10.1016/j.dam.2013.11.015">Counting inequivalent monotone Boolean functions</a>, Discrete Applied Mathematics, 167 (2014), 15-24.
%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BooleanFunction.html">Boolean Function</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 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F a(n) = A306505(n) + 1. - _Gus Wiseman_, Jul 02 2019
%e From _Gus Wiseman_, Feb 20 2019: (Start)
%e Non-isomorphic representatives of the a(0) = 2 through a(3) = 10 antichains:
%e {} {} {} {}
%e {{}} {{}} {{}} {{}}
%e {{1}} {{1}} {{1}}
%e {{1,2}} {{1,2}}
%e {{1},{2}} {{1},{2}}
%e {{1,2,3}}
%e {{1},{2,3}}
%e {{1},{2},{3}}
%e {{1,3},{2,3}}
%e {{1,2},{1,3},{2,3}}
%e (End)
%Y Cf. A000372, A007153, A006602, A007411.
%Y Cf. A006126, A014466, A261005, A293606, A293993, A304996, A305000, A305857, A306505, A319721, A320449, A321679.
%Y Cf. A007363, A046165, A306007, A307249, A326358, A326363.
%K nonn,hard,nice,more
%O 0,1
%A _N. J. A. Sloane_
%E a(7) added by _Timothy Yusun_, Sep 27 2012
%E a(8) from Pawelski added by _Michel Marcus_, Sep 01 2021
%E a(9) from Pawelski added by _Michel Marcus_, May 11 2023
|
