A001206 -id:A001206 - cp's OEIS frontend

A001087 Related to S(n), the number of self-dual monotone Boolean functions of n variables (A001206): 2^n-th term is S(n).

1, 2, 3, 4, 5, 7, 11, 12, 13, 18, 26, 31, 49, 62, 80, 81, 82, 101, 126, 167, 215, 295, 417, 436, 602, 887, 1371, 1454, 2332, 2479, 2645, 2646

Offset: 1

M. Roller [ Martin.Roller(AT)mathematik.uni-regensburg.de ]

This sequence needs a definition!

Index entries for sequences related to Boolean functions

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

A305843 Number of labeled spanning intersecting set-systems on n vertices.

Original entry on oeis.org

1, 1, 3, 27, 1245, 1308285, 912811093455, 291201248260060977862887, 14704022144627161780742038728709819246535634969, 12553242487940503914363982718112298267975272588471811456164576678961759219689708372356843289

Offset: 0

Gus Wiseman, Jun 11 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge.

			The a(3) = 27 spanning intersecting set-systems:
{{1,2,3}}
{{1},{1,2,3}}
{{2},{1,2,3}}
{{3},{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,2},{1,2,3}}
{{1,3},{2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{1,2,3}}
{{1},{1,3},{1,2,3}}
{{2},{1,2},{2,3}}
{{2},{1,2},{1,2,3}}
{{2},{2,3},{1,2,3}}
{{3},{1,3},{2,3}}
{{3},{1,3},{1,2,3}}
{{3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1},{1,2},{1,3},{1,2,3}}
{{2},{1,2},{2,3},{1,2,3}}
{{3},{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A048143, A051185, A134958, A030019, A304985, A305844.

Length/@Table[Select[Subsets[Rest[Subsets[Range[n]]]],And[Union@@#==Range[n],FreeQ[Intersection@@@Tuples[#,2],{}]]&],{n,1,4}]

Inverse binomial transform of A051185.

A305854 Number of unlabeled spanning intersecting set-systems on n vertices.

Original entry on oeis.org

1, 1, 2, 10, 110, 14868, 1289830592

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge.

			Non-isomorphic representatives of the a(3) = 10 spanning intersecting set-systems:
  {{1,2,3}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{2,3},{1,2,3}}
  {{3},{1,3},{2,3}}
  {{3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{3},{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A051185, A261006, A283877, A304998, A305843, A305844, A305855-A305857.

a(n) = A305856(n) - A305856(n-1) for n > 0. - Andrew Howroyd, Aug 12 2019

a(5) from Andrew Howroyd, Aug 12 2019

a(6) from Bert Dobbelaere, Apr 28 2025

A305844 Number of labeled spanning intersecting antichains on n vertices.

Original entry on oeis.org

1, 1, 1, 5, 50, 2330, 1407712, 229800077244, 423295097236295093695

Offset: 0

Gus Wiseman, Jun 11 2018

nonn

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. S is spanning if every vertex is contained in some edge.

			The a(3) = 5 spanning intersecting antichains:
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}

Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Cf. A001206, A006126, A048143, A051185, A134958, A030019, A304985, A305843.

Length/@Table[Select[Subsets[Rest[Subsets[Range[n]]]],And[Union@@#==Range[n],FreeQ[Intersection@@@Tuples[#,2],{},{1}],Select[Tuples[#,2],UnsameQ@@#&&Complement@@#=={}&]=={}]&],{n,1,4}]

Inverse binomial transform of A001206(n + 1).

A305857 Number of unlabeled intersecting antichains on up to n vertices.

Original entry on oeis.org

1, 2, 3, 6, 15, 87, 3528, 47174113

Offset: 0

Gus Wiseman, Jun 11 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.

			Non-isomorphic representatives of the a(4) = 15 intersecting antichains:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{1,2,3,4}}
  {{1,3},{2,3}}
  {{1,4},{2,3,4}}
  {{1,3,4},{2,3,4}}
  {{1,2},{1,3},{2,3}}
  {{1,4},{2,4},{3,4}}
  {{1,3},{1,4},{2,3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,2,4},{1,3,4},{2,3,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Cf. A001206, A006126, A051185, A261006, A283877, A304998, A305843, A305844, A305854, A305855, A305856.

a(n) = A305855(0) + A305855(1) + ... + A305855(n). - Brendan McKay, May 11 2020

a(6) from Andrew Howroyd, Aug 13 2019

a(7) from Brendan McKay, May 11 2020

A007363 Maximal self-dual antichains on n points.

Original entry on oeis.org

0, 1, 3, 5, 20, 168, 11748, 12160647

Offset: 1

N. J. A. Sloane

From Gus Wiseman, Jul 02 2019: (Start)
If self-dual means (pairwise) intersecting, then a(n) is the number of maximal intersecting antichains of nonempty subsets of {1..(n - 1)}. A set of sets is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint. For example, the a(2) = 1 through a(5) = 20 maximal intersecting antichains are:
   {1}    {1}     {1}             {1}
          {2}     {2}             {2}
          {12}    {3}             {3}
                  {123}           {4}
                  {12}{13}{23}    {1234}
                                  {12}{13}{23}
                                  {12}{14}{24}
                                  {13}{14}{34}
                                  {23}{24}{34}
                                  {12}{134}{234}
                                  {13}{124}{234}
                                  {14}{123}{234}
                                  {23}{124}{134}
                                  {24}{123}{134}
                                  {34}{123}{124}
                                  {12}{13}{14}{234}
                                  {12}{23}{24}{134}
                                  {13}{23}{34}{124}
                                  {14}{24}{34}{123}
                                  {123}{124}{134}{234}
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Daniel E. Loeb, On Games, Voting Schemes and Distributive Lattices. LaBRI Report 625-93, University of Bordeaux I, 1993. [Broken link]

Intersecting antichains are A326372.
Intersecting antichains of nonempty sets are A001206.
Unlabeled intersecting antichains are A305857.
Maximal antichains of nonempty sets are A326359.
The case with empty edges allowed is A326363.
Cf. A000372, A305844, A306007, A326358, A326361, A326362, A326366.

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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]]],{n,0,5}] (* Gus Wiseman, Jul 02 2019 *)
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
Length[sets]-1 (* Elijah Beregovsky, May 06 2020 *)

For n > 0, a(n) = A326363(n - 1) - 1 = A326362(n - 1) + n - 1. - Gus Wiseman, Jul 03 2019

a(8) from Elijah Beregovsky, May 06 2020

A305999 Number of unlabeled spanning intersecting set-systems on n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 6, 76, 12916

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge. A singleton is an edge containing only one vertex.

			Non-isomorphic representative of the a(3) = 6 set-systems:
{{1,2,3}}
{{1,3},{2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A051185, A048143, A261006, A058891, A261005, A304998, A305854-A305857, A305935, A306000, A306001, A306008.

a(n) = A306001(n) - A306001(n-1) for n > 0. - Andrew Howroyd, Aug 12 2019

a(5) from Andrew Howroyd, Aug 12 2019

A326366 Number of intersecting antichains of nonempty subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).

Original entry on oeis.org

1, 1, 1, 2, 28, 1960, 1379273, 229755337549, 423295079757497714059

Offset: 0

Gus Wiseman, Jul 01 2019

A set system (set of sets) is an antichain if no edge is a subset of any other, and is intersecting if no two edges are disjoint.

			The a(0) = 1 through a(4) = 28 intersecting antichains with empty intersection:
  {}  {}  {}  {}              {}
              {{12}{13}{23}}  {{12}{13}{23}}
                              {{12}{14}{24}}
                              {{13}{14}{34}}
                              {{23}{24}{34}}
                              {{12}{13}{234}}
                              {{12}{14}{234}}
                              {{12}{23}{134}}
                              {{12}{24}{134}}
                              {{13}{14}{234}}
                              {{13}{23}{124}}
                              {{13}{34}{124}}
                              {{14}{24}{123}}
                              {{14}{34}{123}}
                              {{23}{24}{134}}
                              {{23}{34}{124}}
                              {{24}{34}{123}}
                              {{12}{134}{234}}
                              {{13}{124}{234}}
                              {{14}{123}{234}}
                              {{23}{124}{134}}
                              {{24}{123}{134}}
                              {{34}{123}{124}}
                              {{12}{13}{14}{234}}
                              {{12}{23}{24}{134}}
                              {{13}{23}{34}{124}}
                              {{14}{24}{34}{123}}
                              {{123}{124}{134}{234}}

The case with empty edges allowed is A326375.
Intersecting antichains of nonempty sets are A001206.
Intersecting set systems with empty intersection are A326373.
Antichains of nonempty sets with empty intersection are A006126 or A307249.
The inverse binomial transform is the covering case A326365.
Cf. A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326361, A326362, A326363, A326364.

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[Select[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&],#=={}||Intersection@@#=={}&]],{n,0,4}]

a(n) = A326375(n) - 1.

a(n) = A001206(n+1) + A307249(n) - A014466(n). - Andrew Howroyd, Aug 14 2019

a(7)-a(8) from Andrew Howroyd, Aug 14 2019

A007007 Valence of graph of maximal intersecting families of sets.

Original entry on oeis.org

0, 1, 3, 4, 10, 15, 35, 56, 126, 210, 462, 792, 1716, 3003, 6435, 11440, 24310, 43758, 92378, 167960, 352716, 646646, 1352078, 2496144, 5200300, 9657700, 20058300, 37442160, 77558760, 145422675, 300540195, 565722720, 1166803110, 2203961430

Offset: 1

Daniel E. Loeb

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jan C. Bioch and Toshihide Ibaraki, Generating and approximating nondominated coteries, IEEE Transactions on parallel and distributed systems 6 (1995), 905-914.
D. E. Loeb and A. Meyerowitz, The maximal intersecting family of sets graph, in H. Barcelo and G. Kalai, editors, Proceedings of the Conference on Jerusalem Combinatorics 1993. AMS series Contemporary Mathematics, 1994.
A. Meyerowitz, Maximal intersecting families, European J. Combin. 16 (1995), no. 5, 491-501.

Cf. A001206, A007006, A007008.

Equals A037952 except for n=1 [Loeb & Meyerowitz, theorem 16]. - Andrey Zabolotskiy, Sep 19 2017

More terms from Andrey Zabolotskiy, Sep 19 2017

cp's OEIS Frontend

A001087 Related to S(n), the number of self-dual monotone Boolean functions of n variables (A001206): 2^n-th term is S(n).

Views

Author

Keywords

Comments

Links

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

A305843 Number of labeled spanning intersecting set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A305854 Number of unlabeled spanning intersecting set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A305844 Number of labeled spanning intersecting antichains on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A305857 Number of unlabeled intersecting antichains on up to n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A007363 Maximal self-dual antichains on n points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A305999 Number of unlabeled spanning intersecting set-systems on n vertices with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A326366 Number of intersecting antichains of nonempty subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).

Views