login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014466 Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set. 71
1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A monotone Boolean function is an increasing functions from P(S), the set of subsets of S, to {0,1}.

The count of antichains includes the antichain consisting of only the empty set, but excludes the empty antichain.

Also counts bases of hereditary systems.

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

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

REFERENCES

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

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).

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.

G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.

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

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.

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.

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

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.

S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.

D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

LINKS

Table of n, a(n) for n=0..8.

K. Atanassov, On Some of Smarandache's Problems.

K. S. Brown, Dedekind's problem.

Winfried Bruns, Pedro A. García-Sánchez, and Luca Moci, The monoid of monotone functions on a poset and arithmetic multiplicities for uniform matroids, arXiv:1902.00864 [math.CO], 2019.

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. - N. J. A. Sloane, Oct 23 2012

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.

Fan Cheng and Vincent Y. F. Tan, A Numerical Study on the Wiretap Network with a Simple Network Topology, arXiv preprint arXiv:1505.02862 [cs.IT], 2015.

Jean Dezert, Foundations for a new theory for plausible and paradoxical reasoning, Tech. Rep. DTIM/IED, ONERA, Paris, pp. 14-15, 2002.

Jean Dezert, Combination of paradoxical sources of information within the neutrosophic framework, Proceedings of the First International Conference on Neutrosophics (2001).

J. L. King, Brick tiling and monotone Boolean functions.

J. L. King, A change-of-coordinates from Geometry to Algebra applied to brick tilings, arXiv:math/9809176 [math.CO], 1998.

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

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.

Y. Nardi and A. Rinaldo, The log-linear group-lasso estimator and its asymptotic properties, Bernoulli 18(3) (2012), 945-974; see Table 2 on p. 954.

Eric Weisstein's World of Mathematics, Antichain.

R. I. P. Wickramasinghe, Topics in log-linear models, 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]

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

Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Index entries for sequences related to Boolean functions

FORMULA

Binomial transform of A307249 (or A006126 if its zeroth term is 1). - Gus Wiseman, Feb 20 2019

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

EXAMPLE

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

From Gus Wiseman, Feb 20 2019: (Start)

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

  {{}}  {{}}   {{}}      {{}}

        {{1}}  {{1}}     {{1}}

               {{2}}     {{2}}

               {{12}}    {{3}}

               {{1}{2}}  {{12}}

                         {{13}}

                         {{23}}

                         {{123}}

                         {{1}{2}}

                         {{1}{3}}

                         {{2}{3}}

                         {{1}{23}}

                         {{2}{13}}

                         {{3}{12}}

                         {{12}{13}}

                         {{12}{23}}

                         {{13}{23}}

                         {{1}{2}{3}}

                         {{12}{13}{23}}

(End)

MATHEMATICA

nn=5;

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]]]];

Table[Length[stableSets[Subsets[Range[n], {1, n}], SubsetQ]], {n, 0, nn}] (* Gus Wiseman, Feb 20 2019 *)

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

A@372 - 1 (* Jean-François Alcover, Jan 07 2020 *)

CROSSREFS

Equals A000372 - 1 = A007153 + 1.

Cf. A003182, A005465, A006126, A006602, A261005, A293606, A304996, A305000, A306505, A307249, A317674, A319721, A320449, A321679.

Sequence in context: A039719 A332653 A198203 * A304981 A284860 A108799

Adjacent sequences:  A014463 A014464 A014465 * A014467 A014468 A014469

KEYWORD

nonn,hard,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

Additional comments from Michael Somos, Jun 10 2002

STATUS

approved

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 November 29 14:50 EST 2021. Contains 349416 sequences. (Running on oeis4.)