|
%I #94 Apr 25 2023 05:15:55
%S 1,2,5,19,167,7580,7828353,2414682040997,56130437228687557907787,
%T 286386577668298411128469151667598498812365
%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
%C From _Lorenzo Sauras Altuzarra_, Apr 02 2023: (Start)
%C a(n) is the number of labeled abstract simplicial complexes on n vertices.
%C A058673(n) <= a(n) <= A058891(n+1). (End)
%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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Abstract_simplicial_complex">Abstract simplicial complex</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 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)
%e From _Lorenzo Sauras Altuzarra_, Apr 02 2023: (Start)
%e The 19 sets E such that ({1, 2, 3}, E) is an abstract simplicial complex:
%e {}
%e {{1}}
%e {{2}}
%e {{3}}
%e {{1}, {2}}
%e {{1}, {3}}
%e {{2}, {3}}
%e {{1}, {2}, {3}}
%e {{1}, {2}, {1, 2}}
%e {{1}, {3}, {1, 3}}
%e {{2}, {3}, {2, 3}}
%e {{1}, {2}, {3}, {1, 2}}
%e {{1}, {2}, {3}, {1, 3}}
%e {{1}, {2}, {3}, {2, 3}}
%e {{1}, {2}, {3}, {1, 2}, {1, 3}}
%e {{1}, {2}, {3}, {1, 2}, {2, 3}}
%e {{1}, {2}, {3}, {1, 3}, {2, 3}}
%e {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}
%e {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
%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, A058673 (labeled matroids), A058891 (labeled hypergraphs), A261005, A293606, A304996, A305000, A306505, A307249, A317674, A319721, A320449, A321679.
%K nonn,hard,more,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
%E Term a(9) (using A000372) from _Joerg Arndt_, Apr 07 2023
|
