A007411 -id:A007411 - cp's OEIS frontend

A293606 Number of unlabeled antichains of weight n.

1, 1, 2, 3, 6, 9, 20, 33, 72, 139

Offset: 0

Gus Wiseman, Oct 13 2017

An antichain is a finite set of finite nonempty sets, none of which is a subset of any other. The weight of an antichain is the sum of cardinalities of its elements.
From Gus Wiseman, Aug 15 2019: (Start)
Also the number of non-isomorphic set multipartitions (multisets of sets) of weight n where every vertex is the unique common element of some subset of the edges. For example, the a(1) = 1 through a(6) = 20 set multipartitions are:
  {1}  {1}{1}  {1}{1}{1}  {1}{2}{12}    {1}{2}{2}{12}    {12}{13}{23}
       {1}{2}  {1}{2}{2}  {1}{1}{1}{1}  {1}{2}{3}{23}    {1}{2}{12}{12}
               {1}{2}{3}  {1}{1}{2}{2}  {1}{1}{1}{1}{1}  {1}{2}{13}{23}
                          {1}{2}{2}{2}  {1}{1}{2}{2}{2}  {1}{2}{3}{123}
                          {1}{2}{3}{3}  {1}{2}{2}{2}{2}  {1}{1}{2}{2}{12}
                          {1}{2}{3}{4}  {1}{2}{2}{3}{3}  {1}{1}{2}{3}{23}
                                        {1}{2}{3}{3}{3}  {1}{2}{2}{2}{12}
                                        {1}{2}{3}{4}{4}  {1}{2}{3}{3}{23}
                                        {1}{2}{3}{4}{5}  {1}{2}{3}{4}{34}
                                                         {1}{1}{1}{1}{1}{1}
                                                         {1}{1}{1}{2}{2}{2}
                                                         {1}{1}{2}{2}{2}{2}
                                                         {1}{1}{2}{2}{3}{3}
                                                         {1}{2}{2}{2}{2}{2}
                                                         {1}{2}{2}{3}{3}{3}
                                                         {1}{2}{3}{3}{3}{3}
                                                         {1}{2}{3}{3}{4}{4}
                                                         {1}{2}{3}{4}{4}{4}
                                                         {1}{2}{3}{4}{5}{5}
                                                         {1}{2}{3}{4}{5}{6}
(End)

			Non-isomorphic representatives of the a(5) = 9 antichains are:
((12345)),
((1)(2345)), ((12)(134)), ((12)(345)),
((1)(2)(345)), ((1)(23)(45)), ((2)(13)(14)),
((1)(2)(3)(45)),
((1)(2)(3)(4)(5)).

Cf. A006126, A006602, A007411, A007716, A048143, A049311, A283877, A293607.

Cf. A000372, A000612, A003182, A014466, A055621, A293993, A326704, A326972.

Euler transform of A293607.

A003182 Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.

Original entry on oeis.org

2, 3, 5, 10, 30, 210, 16353, 490013148, 1392195548889993358, 789204635842035040527740846300252680

Offset: 0

N. J. A. Sloane

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
First differs from A348260(n + 1) at a(5) = 210, A348260(6) = 233. - Gus Wiseman, Nov 28 2021
Pawelski & Szepietowski show that a(n) = A001206(n) (mod 2) and that a(9) = 6 (mod 210). - Charles R Greathouse IV, Feb 16 2023

			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)

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

K. S. Brown, Dedekind's problem
Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See pp. 2, 14.
Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.
Patrick De Causmaecker and Lennart Van Hirtum, Solving systems of equations on antichains for the computation of the ninth Dedekind Number, arXiv:2405.20904 [math.CO], 2024. See p. 4.
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.
Sascha 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 and 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]
Bartlomiej Pawelski, On the number of inequivalent monotone Boolean functions of 8 variables, arXiv:2108.13997 [math.CO], 2021. See Table 2 p. 2.
Bartlomiej Pawelski, On the number of inequivalent monotone Boolean functions of 9 variables, arXiv:2305.06346 [math.CO], 2023.
Bartłomiej Pawelski, Counting and generating monotone Boolean functions, Doctoral Diss., Univ. Gdańsk, (Poland, 2024). See pp. 12, 24, 34-35, 40, 49-50.
Bartlomiej Pawelski and Andrzej Szepietowski, Divisibility properties of Dedekind numbers, arXiv:2302.04615 [math.CO], 2023.
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.
Andrzej Szepietowski, Fixes of permutations acting on monotone Boolean functions, arXiv:2205.03868 [math.CO], 2022. See p. 17.
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

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.

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

a(7) added by Timothy Yusun, Sep 27 2012
a(8) from Pawelski added by Michel Marcus, Sep 01 2021
a(9) from Pawelski added by Michel Marcus, May 11 2023

A261005 Number of unlabeled simplicial complexes with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210, 789204635842035039135545297410259322

Offset: 0

N. J. A. Sloane, Aug 13 2015

nonn

Also the number of non-isomorphic antichains of nonempty sets covering n vertices. The labeled case is A006126, except with a(0) = 1. - Gus Wiseman, Feb 23 2019

			From _Gus Wiseman_, Feb 23 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(4) = 20 antichains:
  {}  {{1}}  {{12}}    {{123}}         {{1234}}
             {{1}{2}}  {{1}{23}}       {{1}{234}}
                       {{13}{23}}      {{12}{34}}
                       {{1}{2}{3}}     {{14}{234}}
                       {{12}{13}{23}}  {{1}{2}{34}}
                                       {{134}{234}}
                                       {{1}{24}{34}}
                                       {{1}{2}{3}{4}}
                                       {{13}{24}{34}}
                                       {{14}{24}{34}}
                                       {{13}{14}{234}}
                                       {{12}{134}{234}}
                                       {{1}{23}{24}{34}}
                                       {{124}{134}{234}}
                                       {{12}{13}{24}{34}}
                                       {{14}{23}{24}{34}}
                                       {{12}{13}{14}{234}}
                                       {{123}{124}{134}{234}}
                                       {{13}{14}{23}{24}{34}}
                                       {{12}{13}{14}{23}{24}{34}}
(End)

Benoît Jubin, Posting to Sequence Fans Mailing List, Aug 12 2015.

C. Lienkaemper, A. Shiu, and Z. Woodstock, Obstructions to convexity in neural codes, Preprint 2015.
Francisco Ponce Carrión and Seth Sullivant, Marginal Independence and Partial Set Partitions, arXiv:2402.16292 [math.ST], 2024. See p. 21.
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Apart from a(0), same as A006602, and after subtracting 1, A007411.

Cf. A000372, A003182, A006126, A014466, A261006, A304997, A304998, A306505, A306550, A321679.

First differences of A306505. - Gus Wiseman, Feb 23 2019

a(n) = A003182(n) - A003182(n-1) for n > 0. - Andrew Howroyd, May 28 2023

a(8)-a(9) added using A003182 by Andrew Howroyd, May 28 2023

A006602 a(n) is the number of hierarchical models on n unlabeled factors or variables with linear terms forced.

Original entry on oeis.org

2, 1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210, 789204635842035039135545297410259322

Offset: 0

Colin Mallows

Also number of pure (= irreducible) group-testing histories of n items - A. Boneh, Mar 31 2000
Also number of antichain covers of an unlabeled n-set, so a(n) equals first differences of A003182. - Vladeta Jovovic, Goran Kilibarda, Aug 18 2000
Also number of inequivalent (under permutation of variables) nondegenerate monotone Boolean functions of n variables. We say h and g (functions of n variables) are equivalent if there exists a permutation p of S_n such that hp=g. E.g., a(3)=5 because xyz, xy+xz+yz, x+yz+xyz, xy+xz+xyz, x+y+z+xy+xz+yz+xyz are 5 inequivalent nondegenerate monotone Boolean functions that generate (by permutation of variables) the other 4. For example, y+xz+xyz can be obtained from x+yz+xyz by exchanging x and y. - Alan Veliz-Cuba (alanavc(AT)vt.edu), Jun 16 2006
The non-spanning/covering case is A003182. The labeled case is A006126. - Gus Wiseman, Feb 20 2019

			From _Gus Wiseman_, Feb 20 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(4) = 20 antichains:
  {}    {{1}}  {{12}}    {{123}}         {{1234}}
  {{}}         {{1}{2}}  {{1}{23}}       {{1}{234}}
                         {{13}{23}}      {{12}{34}}
                         {{1}{2}{3}}     {{14}{234}}
                         {{12}{13}{23}}  {{1}{2}{34}}
                                         {{134}{234}}
                                         {{1}{24}{34}}
                                         {{1}{2}{3}{4}}
                                         {{13}{24}{34}}
                                         {{14}{24}{34}}
                                         {{13}{14}{234}}
                                         {{12}{134}{234}}
                                         {{1}{23}{24}{34}}
                                         {{124}{134}{234}}
                                         {{12}{13}{24}{34}}
                                         {{14}{23}{24}{34}}
                                         {{12}{13}{14}{234}}
                                         {{123}{124}{134}{234}}
                                         {{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{34}}
(End)

Y. M. M. Bishop, S. E. Fienberg and P. W. Holland, Discrete Multivariate Analysis. MIT Press, 1975, p. 34. [In part (e), the Hierarchy Principle for log-linear models is defined. It essentially says that if a higher-order parameter term is included in the log-linear model, then all the lower-order parameter terms should also be included. - Petros Hadjicostas, Apr 10 2020]
V. Jovovic and G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.
A. A. Mcintosh, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See p. 14.
V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11(4) (1999), 127-138 (translated in Discrete Mathematics and Applications, 9(6) (1999), 593-605).
C. Lienkaemper, When do neural codes come from convex or good covers?, 2015.
C. L. Mallows, Emails to N. J. A. Sloane, Jun-Jul 1991
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Cf. A000372, A003182, A006126 (labeled case), A007411, A014466, A261005, A293993, A304997, A304998, A304999, A305001, A305855, A306505, A320449, A321679.

a(n) = A007411(n) + 1.

First differences of A003182. - Gus Wiseman, Feb 23 2019

a(6) from A. Boneh, 32 Hantkeh St., Haifa 34608, Israel, Mar 31 2000
Entry revised by N. J. A. Sloane, Jul 23 2006
a(7) from A007411 and A003182. - N. J. A. Sloane, Aug 13 2015
Named edited by Petros Hadjicostas, Apr 08 2020
a(8) from A003182. - Bartlomiej Pawelski, Nov 27 2022
a(9) from A007411. - Dmitry I. Ignatov, Nov 27 2023

A306007 Number of non-isomorphic intersecting antichains of weight n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 6, 6, 14, 22

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. The weight of S is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(8) = 14 set-systems:
{{1,2,3,4,5,6,7,8}}
{{1,7},{2,3,4,5,6,7}}
{{1,2,7},{3,4,5,6,7}}
{{1,5,6},{2,3,4,5,6}}
{{1,2,3,7},{4,5,6,7}}
{{1,2,5,6},{3,4,5,6}}
{{1,3,4,5},{2,3,4,5}}
{{1,2},{1,3,4},{2,3,4}}
{{1,4},{1,5},{2,3,4,5}}
{{1,5},{2,4,5},{3,4,5}}
{{1,6},{2,6},{3,4,5,6}}
{{1,6},{2,3,6},{4,5,6}}
{{2,4},{1,2,5},{3,4,5}}
{{1,5},{2,5},{3,5},{4,5}}

Cf. A007411, A007716, A034691, A048143, A049311, A116540, A283877, A293606, A293607, A304867, A305999, A305854-A305857, A306005-A306008.

cp's OEIS Frontend

A293606 Number of unlabeled antichains of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A003182 Dedekind numbers: inequivalent monotone Boolean functions of n or fewer variables, or antichains of subsets of an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A261005 Number of unlabeled simplicial complexes with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A006602 a(n) is the number of hierarchical models on n unlabeled factors or variables with linear terms forced.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A306007 Number of non-isomorphic intersecting antichains of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A037843 Number of matrices with n columns whose rows do not cover each other; ordered antichains of subsets of an n-set.

Views

Author

Keywords

References

Links

Crossrefs

Formula