The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 64


%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 A307249. This sequence has a similar description to A305000 except that the singletons must be disjoint from the other edges. - _Gus Wiseman_, Feb 20 2019

%C a(n) is the total number of hierarchical log-linear models on n labeled factors (categorical variables). See Wickramasinghe (2008) and Nardi and Rinaldo (2012). - _Petros Hadjicostas_, Apr 08 2020

%D I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.

%D Jorge Luis Arocha, "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21 (1987).

%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 J. Dezert, Fondations pour une nouvelle théorie 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 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.

%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 Winfried Bruns, Pedro A. García-Sánchez, and Luca Moci, <a href="https://arxiv.org/abs/1902.00864">The monoid of monotone functions on a poset and arithmetic multiplicities for uniform matroids</a>, arXiv:1902.00864 [math.CO], 2019.

%H Donald E. Campbell, Jack Graver, and Jerry S. Kelly, <a href="https://doi.org/10.1016/j.mathsocsci.2012.05.001">There are more strategy-proof procedures than you think</a>, Mathematical Social Sciences 64 (2012) 263-265. - _N. J. A. Sloane_, Oct 23 2012

%H Fan Cheng, <a href="https://doi.org/10.1109/ISIT.2014.6874940">Optimality of routing on the wiretap network with simple network topology</a>, Information Theory (ISIT), 2014 IEEE International Symposium on, June 29 2014-July 4 2014 Page(s): 786 - 790 INSPEC Accession Number: 14524545 Honolulu, HI.

%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 [cs.IT], 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 J. L. King, <a href="https://arxiv.org/abs/math/9809176">A change-of-coordinates from Geometry to Algebra applied to brick tilings</a>, arXiv:math/9809176 [math.CO], 1998.

%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 Y. Nardi and A. Rinaldo, <a href="https://projecteuclid.org/euclid.bj/1340887009">The log-linear group-lasso estimator and its asymptotic properties</a>, Bernoulli 18(3) (2012), 945-974; see Table 2 on p. 954.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Antichain.html">Antichain</a>.

%H R. I. P. Wickramasinghe, <a href="http://hdl.handle.net/2346/20089">Topics in log-linear models</a>, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008. [For n = 2, the a(2) = 5 hierarchical log-linear models on two factors X and Y appear on p. 18. For n = 3, the a(3) = 19 hierarchical log-linear models on three factors X, Y, and Z, appear on p. 36. - _Petros Hadjicostas_, Apr 08 2020]

%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 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 A307249 (or A006126 if its zeroth term is 1). - _Gus Wiseman_, Feb 20 2019

%F a(n) >= A005465(n) (because the hierarchical log-linear models on n factors always include all the conditional independence models considered by I. J. Good in A005465). - _Petros Hadjicostas_, Apr 24 2020

%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 *)

%t A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {_, _}][[All, 2]]];

%t A@372 - 1 (* _Jean-François Alcover_, Jan 07 2020 *)

%Y Equals A000372 - 1 = A007153 + 1.

%Y Cf. A003182, A005465, A006126, A006602, A261005, A293606, A304996, A305000, A306505, A307249, 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 February 24 18:29 EST 2021. Contains 341577 sequences. (Running on oeis4.)