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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003182 Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.
(Formerly M0729)
32
2, 3, 5, 10, 30, 210, 16353, 490013148 (list; graph; refs; listen; history; text; internal format)
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

The labeled case is A000372. - Gus Wiseman, Feb 23 2019

From Gus Wiseman, Jul 02 2019: (Start)

Also the number of unlabeled maximal antichains of subsets of {1..(n + 1)}. For example, non-isomorphic representatives of the a(-1) = 1 through a(3) = 10 antichains are:

  {}  {}   {}      {}            {}

      {1}  {12}    {123}         {1234}

           {1}{2}  {1}{23}       {1}{234}

                   {1}{2}{3}     {1}{2}{34}

                   {12}{13}{23}  {1}{2}{3}{4}

                                 {12}{134}{234}

                                 {1}{23}{24}{34}

                                 {12}{13}{14}{234}

                                 {123}{124}{134}{234}

                                 {12}{13}{14}{23}{24}{34}

(End)

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

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

K. S. Brown, Dedekind's problem

Patrick De Causmaecker, Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Liviu Ilinca, and Jeff Kahn, Counting maximal antichains and independent sets, arXiv:1202.4427 [math.CO], 2012; Order 30.2 (2013): 427-435.

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

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.

S. Kurz, Competitive learning of monotone Boolean functions, arXiv:1401.8135 [cs.DS], 2014.

C. L. Mallows, Emails to N. J. A. Sloane, Jun-Jul 1991

Mikaël Monet, Dan Olteanu, Towards Deterministic Decomposable Circuits for Safe Queries, 2018.

S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]

Tamon Stephen and Timothy Yusun, Counting inequivalent monotone Boolean functions, Discrete Applied Mathematics, 167 (2014), 15-24.

Tamon Stephen and Timothy Yusun, Counting inequivalent monotone Boolean functions, arXiv preprint arXiv:1209.4623 [cs.DS], 2012.

Eric Weisstein's World of Mathematics, Boolean Function.

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

a(n) = A306505(n) + 1. - Gus Wiseman, Jul 02 2019

EXAMPLE

From Gus Wiseman, Feb 20 2019: (Start)

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. A000372, A007153, A006602, A007411.

Cf. A006126, A014466, A261005, A293606, A293993, A304996, A305000, A305857, A306505, A319721, A320449, A321679.

Cf. A007363, A046165, A306007, A307249, A326358, A326363.

Sequence in context: A003504 A213169 A330333 * A134294 A154956 A197312

Adjacent sequences:  A003179 A003180 A003181 * A003183 A003184 A003185

KEYWORD

nonn,hard,nice,more

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(7) added by Timothy Yusun, Sep 27 2012

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 27 06:19 EST 2020. Contains 338678 sequences. (Running on oeis4.)