|
|
A003182
|
|
Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.
(Formerly M0729)
|
|
40
|
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
NP-equivalence classes of unate Boolean functions of n or fewer variables.
Also the number of simple games with n players in minimal winning form up to isomorphism. - Fabián Riquelme, Mar 13 2018
|
|
REFERENCES
|
I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
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.
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.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
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, Table 2.3.2. - Row 13.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. H. Wiedemann, personal communication.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(0) = 2 through a(3) = 10 antichains:
{} {} {} {}
{{}} {{}} {{}} {{}}
{{1}} {{1}} {{1}}
{{1,2}} {{1,2}}
{{1},{2}} {{1},{2}}
{{1,2,3}}
{{1},{2,3}}
{{1},{2},{3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
(End)
|
|
CROSSREFS
|
Cf. A006126, A014466, A261005, A293606, A293993, A304996, A305000, A305857, A306505, A319721, A320449, A321679.
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|