This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014466 Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set. 15


%S 1,2,5,19,167,7580,7828353,2414682040997,56130437228687557907787

%N Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set.

%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 antichain consisting of only the empty set, but excludes the empty antichain.

%C Also counts bases of hereditary systems.

%C Also antichains of nonempty subsets of an n-set. The unlabeled case is A306505. The spanning case is A006126. This sequence has a similar description to A305000 except that the singletons must be disjoint from the other edges. - _Gus Wiseman_, Feb 20 2019

%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 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. - From _N. J. A. Sloane_, Oct 23 2012

%D Fan Cheng, Optimality of routing on the wiretap network with simple network topology, Information Theory (ISIT), 2014 IEEE International Symposium on, June 29 2014-July 4 2014 Page(s): 786 - 790 INSPEC Accession Number: 14524545 Honolulu, HI DOI: 10.1109/ISIT.2014.6874940

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.

%D J. Dezert, Fondations pour une nouvelle theorie du raisonnement plausible et paradoxal (la DSmT), Tech. Rep. 1/06769 DTIM, ONERA, Paris, page 33, January 2003.

%D J. Dezert, F. Smarandache, On the generating of hyper-powersets for the DSmT, Proceedings of the 6th International Conference on Information Fusion, Cairns, Australia, 2003.

%D M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.

%D D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean functions. Proc. Amer. Math. Soc. 21 1969 677-682.

%D 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.

%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 D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

%D D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991) 5-6.

%H K. Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>

%H Fan Cheng and Vincent Y. F. Tan, <a href="http://arxiv.org/abs/1505.02862">A Numerical Study on the Wiretap Network with a Simple Network Topology</a>, arXiv preprint arXiv:1505.02862, 2015.

%H Jean Dezert, <a href="http://www.gallup.unm.edu/~smarandache/IS2002Sept24.pdf">Foundations for a new theory for plausible and paradoxical reasoning</a>, Tech. Rep. DTIM/IED, ONERA, Paris, pp. 14-15, 2002.

%H Jean Dezert, Combination of paradoxical sources of information within the neutrosophic framework, <a href="http://www.gallup.unm.edu/~smarandache/NeutrosophicProceedings.pdf">Proceedings of the First International Conference on Neutrosophics</a> (2001).

%H J. L. King, <a href="http://www.math.ufl.edu/~squash/">Brick tiling and monotone Boolean functions</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Antichain.html">Antichain</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 Binomial transform of A006126. - _Gus Wiseman_, Feb 20 2019

%e a(2)=5 from the antichains {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.

%e From _Gus Wiseman_, Feb 20 2019: (Start)

%e The a(0) = 1 through a(3) = 19 antichains:

%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],{1,n}],SubsetQ]],{n,0,nn}] (* _Gus Wiseman_, Feb 20 2019 *)

%Y Equals A000372 - 1 = A007153 + 1. Cf. A003182.

%Y Cf. A006126, A006602, A261005, A293606, A304996, A305000, A306505, A317674, A319721, A320449, A321679.

%K nonn,hard,nice

%O 0,2

%A _N. J. A. Sloane_.

%E Last term from D. H. Wiedemann, personal communication.

%E Additional comments from _Michael Somos_, Jun 10 2002.

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 04:59 EDT 2019. Contains 321364 sequences. (Running on oeis4.)