|
|
A007153
|
|
Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.
(Formerly M3551 N1439)
|
|
17
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Equivalently, the number of elements of the free distributive lattice with n generators.
A monotone Boolean function is an increasing functions from P(S), the set of subsets of S, to {0,1}.
The count of antichains excludes the empty antichain which contains no subsets and the antichain consisting of only the empty set.
The number of continuous functions f : R^n->R with f(x_1,..,x_n) in {x_1,..,x_n}. - Jan Fricke, Feb 12 2004
a(n) is also the number of reduced normal conjunctive forms with n variables without negation.
For example the 18 forms for n=3 are :
a
b
c
a or b
a or c
b or c
a or b or c
a and b
a and c
b and c
a and (b or c)
b and (a or c)
c and (a or b)
(a or b) and (a or c)
(b or a) and (b or c)
(c or a) and (c or b)
a and b and c
(a or b) and (a or c) and (b or c)
(End)
|
|
REFERENCES
|
I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
J. L. Arocha, (1987) "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21.
R. Balbes and P. Dwinger, Distributive Lattices, Univ. Missouri Press, 1974, see p. 97. - N. J. A. Sloane, Aug 15 2010
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.
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.
|
|
LINKS
|
J. Berman, Free spectra of 3-element algebras, R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983. (Annotated scanned copy)
Eric Weisstein's World of Mathematics, Antichain
|
|
EXAMPLE
|
a(2)=4 from the antichains {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Last term from D. H. Wiedemann, personal communication
|
|
STATUS
|
approved
|
|
|
|