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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006126 Number of hierarchical models with linear terms forced. Also number of antichain covers of a labeled n-set.
(Formerly M1954)
2, 1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966 (list; graph; refs; listen; history; text; internal format)



An antichain cover is a cover such that no element of the cover is a subset of another element of the cover.

Also, the number of nondegenerate monotone boolean functions of n variables in an n-variable boolean algebra. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004

Also, number of simplicial complexes on an n-element vertex set. - Richard Stanley, Feb 10 2019

There are two antichains of size zero, namely {} and {{}}, while there is only one simplicial complex, namely {}. The unlabeled case is A006602. The non-covering case is A000372, which is A014466 plus 1. - Gus Wiseman, Mar 31 2019


Y. M. M. Bishop, S. E. Fienberg and P. W. Holland, Discrete Multivariate Analysis. MIT Press, 1975, p. 34.

V. Jovovic and G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.

C. L. Mallows, personal communication.

A. A. Mcintosh, personal communication.

R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables, In Preparation.

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


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

R. Baumann and H. Strass, On the number of bipolar Boolean functions, to appear (2014).

Florian Bridoux, Nicolas Durbec, Kevin Perrot, Adrien Richard, Complexity of Maximum Fixed Point Problem in Boolean Networks, Conference on Computability in Europe (CiE 2019) Computing with Foresight and Industry (Lecture Notes in Computer Science book series, Vol. 11558), Springer, Cham, 132-143.

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.

V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).

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

C. L. Mallows & N. J. A. Sloane, Emails, May 1991

C. L. Mallows & N. J. A. Sloane, Emails, Jun. 1991

R. A. Obando, Project: A Map of a Rule Space (To be posted)

Eric Weisstein's World of Mathematics, Antichain

Eric Weisstein's World of Mathematics, Cover

D. H. Wiedemann, Letter to N. J. A. Sloane, Nov 03, 1990

D. H. Wiedermann, Email to N. J. A. Sloane, May 28 1991

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


a(n) = Sum_{k=1..C(n, floor(n/2))}b(k, n) where b(k, n) is the number of k-antichain covers of a labeled n-set.

Inverse binomial transform of A000372. - Gus Wiseman, Feb 24 2019


a(5) = 1+90+790+1895+2116+1375+490+115+20+2 = 6894.

There are 9 antichain covers of a labeled 3-set: {{1,2,3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1},{2},{3}}, {{1,2},{1,3},{2,3}}.

From Gus Wiseman, Feb 23 2019: (Start)

The a(0) = 2 through a(3) = 9 antichains:

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

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











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]], SubsetQ], Union@@#==Range[n]&]], {n, 0, nn}] (* Gus Wiseman, Feb 23 2019 *)

A000372 = Cases[Import["https://oeis.org/A000372/b000372.txt", "Table"], {_, _}][[All, 2]];

lg = Length[A000372];

a372[n_] := If[0 <= n <= lg-1, A000372[[n+1]], 0];

a[n_] := Sum[(-1)^(n-k+1) Binomial[n, k-1] a372[k-1], {k, 0, lg}];

a /@ Range[0, lg-1] (* Jean-Fran├žois Alcover, Jan 07 2020 *)


Cf. A000372, A056046-A056049, A056052, A056101, A056104, A051112-A051118.

Cf. A006602, A014466, A261005, A293606, A293993, A305000, A305844, A306550, A307249, A317674, A319721, A320449.

Sequence in context: A271574 A274198 A002079 * A078357 A225432 A086382

Adjacent sequences:  A006123 A006124 A006125 * A006127 A006128 A006129




N. J. A. Sloane


Last 3 terms from Michael Bulmer (mrb(AT)maths.uq.edu.au)

Antichain interpretation from Vladeta Jovovic and Goran Kilibarda, Jul 31 2000

a(0) = 2 added by Gus Wiseman, Feb 23 2019



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 February 17 17:59 EST 2020. Contains 331999 sequences. (Running on oeis4.)