|
%I M3551 N1439 #58 Oct 29 2023 17:28:29
%S 0,1,4,18,166,7579,7828352,2414682040996,56130437228687557907786,
%T 286386577668298411128469151667598498812364
%N Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.
%C Equivalently, the number of elements of the free distributive lattice with n generators.
%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 excludes the empty antichain which contains no subsets and the antichain consisting of only the empty set.
%C The number of continuous functions f : R^n->R with f(x_1,..,x_n) in {x_1,..,x_n}. - _Jan Fricke_, Feb 12 2004
%C From _Robert FERREOL_, Mar 23 2009: (Start)
%C a(n) is also the number of reduced normal conjunctive forms with n variables without negation.
%C For example the 18 forms for n=3 are :
%C a
%C b
%C c
%C a or b
%C a or c
%C b or c
%C a or b or c
%C a and b
%C a and c
%C b and c
%C a and (b or c)
%C b and (a or c)
%C c and (a or b)
%C (a or b) and (a or c)
%C (b or a) and (b or c)
%C (c or a) and (c or b)
%C a and b and c
%C (a or b) and (a or c) and (b or c)
%C (End)
%D I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
%D J. L. Arocha, (1987) "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21.
%D R. Balbes and P. Dwinger, Distributive Lattices, Univ. Missouri Press, 1974, see p. 97. - _N. J. A. Sloane_, Aug 15 2010
%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 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 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 D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.
%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>
%H J. Berman, <a href="/A007153/a007153.pdf">Free spectra of 3-element algebras</a>, R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983. (Annotated scanned copy)
%H R. Church, <a href="https://doi.org/10.1215/S0012-7094-40-00655-X">Numerical analysis of certain free distributive lattices</a>, Duke Math. J., 6 (1940), 732-734.
%H Jacob North Clark, Stephen Montgomery-Smith, <a href="https://arxiv.org/abs/1809.07747">Shapley-like values without symmetry</a>, arXiv:1809.07747 [econ.TH], 2018.
%H J. D. Farley, <a href="https://www.ams.org/notices/202202/rnoti-p190.pdf">Was Gelfand right? The many loves of lattice theory</a>, Notices AMS 69:2 (2022), 190-197.
%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 N. M. Rivière, <a href="https://doi.org/10.1016/S0021-9800(68)80068-7">Recursive formulas on free distributive lattices</a>, J. Combin. Theory, 5 (1968), 229-234. - _N. J. A. Sloane_, Aug 15 2010
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).
%H M. Ward, <a href="https://doi.org/10.1090/S0002-9904-1946-08566-3">Note on the order of the free distributive lattice</a>, Bull. Amer. Math. Soc., (1946), Abstract 52-5-135 p.423. - _N. J. A. Sloane_, Aug 15 2010
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Antichain.html">Antichain</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 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. - _N. J. A. Sloane_, Aug 15 2010
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%e a(2)=4 from the antichains {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
%Y Equals A000372 - 2 and A014466 - 1.. Cf. A003182.
%K nonn,hard,nice
%O 0,3
%A _N. J. A. Sloane_
%E Last term from D. H. Wiedemann, personal communication
%E Additional comments from _Michael Somos_, Jun 10 2002
%E Term a(9) (using A000372) from _Joerg Arndt_, Apr 07 2023
| 