|
|
A014466
|
|
Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set.
|
|
82
|
|
|
|
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
a(n) is the number of labeled abstract simplicial complexes on n vertices.
|
|
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
|
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]
|
|
FORMULA
|
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}}.
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)
The 19 sets E such that ({1, 2, 3}, E) is an abstract simplicial complex:
{}
{{1}}
{{2}}
{{3}}
{{1}, {2}}
{{1}, {3}}
{{2}, {3}}
{{1}, {2}, {3}}
{{1}, {2}, {1, 2}}
{{1}, {3}, {1, 3}}
{{2}, {3}, {2, 3}}
{{1}, {2}, {3}, {1, 2}}
{{1}, {2}, {3}, {1, 3}}
{{1}, {2}, {3}, {2, 3}}
{{1}, {2}, {3}, {1, 2}, {1, 3}}
{{1}, {2}, {3}, {1, 2}, {2, 3}}
{{1}, {2}, {3}, {1, 3}, {2, 3}}
{{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}
{{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
(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]]];
|
|
CROSSREFS
|
Cf. A003182, A005465, A006126, A006602, A058673 (labeled matroids), A058891 (labeled hypergraphs), A261005, A293606, A304996, A305000, A306505, A307249, A317674, A319721, A320449, A321679.
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Last term from D. H. Wiedemann, personal communication.
|
|
STATUS
|
approved
|
|
|
|