A000372 -id:A000372 - cp's OEIS frontend

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

1, 2, 5, 19, 120, 1084, 11783, 141110, 1791156, 23646352, 321220257, 4459886776, 63000867229, 902528825332, 13080523942476, 191445447535373, 2825542818304080, 42005234042942228, 628422035415996065, 9454076958795999908, 142933849346150225253, 2170556938059142024688

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(3) = 19 non-crossing antichains:
  {}  {}     {}        {}
      {{1}}  {{1}}     {{1}}
             {{2}}     {{2}}
             {{12}}    {{3}}
             {{1}{2}}  {{12}}
                       {{13}}
                       {{23}}
                       {{123}}
                       {{1}{2}}
                       {{1}{3}}
                       {{2}{3}}
                       {{1}{23}}
                       {{2}{13}}
                       {{3}{12}}
                       {{12}{13}}
                       {{12}{23}}
                       {{13}{23}}
                       {{1}{2}{3}}
                       {{12}{13}{23}}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000108 (non-crossing set partitions), A000124, A000372 (antichains), A001006, A001263, A006126 (antichain covers), A014466 (nonempty antichains), A054726 (non-crossing graphs), A099947, A261005, A306438.

Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

nn=6;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-2*x))/x) } \\ Andrew Howroyd, Jan 20 2023

Binomial transform of A324167.

G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - Andrew Howroyd, Jan 20 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

A326360 Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.

Original entry on oeis.org

1, 1, 1, 2, 13, 279, 29820, 123590767

Offset: 0

Gus Wiseman, Jul 01 2019

A set system (set of sets) is an antichain if no element is a subset of any other.

			The a(1) = 1 through a(4) = 13 maximal antichains:
  {}  {12}  {123}         {1234}
            {12}{13}{23}  {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}
                          {12}{13}{14}{23}{24}{34}

Dmitry I. Ignatov, On the Number of Maximal Antichains in Boolean Lattices for n up to 7. Lobachevskii J. Math., 44 (2023), 137-146.
Dmitry I. Ignatov, Supporting iPython code and input files for a(7) based on inequivalent maximal antichains for n=7 and related sequences, Github repository, section 3
Dmitry I. Ignatov, PDF version of the supporting iPython notebook for a(7)
Dmitry I. Ignatov, Supporting iPython notebook for a(7): A326360.ipynb

Antichains of nonempty, non-singleton sets are A307249.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A000372, A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305844, A326358, A326361, A326362, A326363.

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],{2,n}],SubsetQ]]],{n,0,4}]

# see Ignatov links
# Dmitry I. Ignatov, Oct 14 2021

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A326359(k) for n >= 2. - Andrew Howroyd, Nov 19 2021

a(6) from Andrew Howroyd, Aug 14 2019

a(7) from Dmitry I. Ignatov, Oct 14 2021

A327057 Number of antichains covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 2, 4, 9, 36, 1572, 3750221

Offset: 0

Gus Wiseman, Aug 18 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. An antichain is a set of sets, none of which is a subset of any other. This sequence counts antichains whose dual is pairwise intersecting.

			The a(0) = 1 through a(3) = 9 antichains:
  {}  {}     {}       {}
      {{1}}  {{1}}    {{1}}
             {{2}}    {{2}}
             {{1,2}}  {{3}}
                      {{1,2}}
                      {{1,3}}
                      {{2,3}}
                      {{1,2,3}}
                      {{1,2},{1,3},{2,3}}

Antichains are A000372.
The BII-numbers of these set-systems are the intersection of A326704 and A326853.
The covering case is A327020.
Cointersecting set-systems are A327039.
Cf. A006126, A051185, A245567, A305844, A326950, A327038, A327052.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
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]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,5}]

Binomial transform of A327020.

A327062 Number of antichains of distinct sets covering a subset of {1..n} whose dual is a weak antichain.

Original entry on oeis.org

1, 2, 5, 16, 81, 2595

Offset: 0

Gus Wiseman, Aug 18 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

			The a(0) = 1 through a(3) = 16 antichains:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1,2}}    {{3}}
             {{1},{2}}  {{1,2}}
                        {{1,3}}
                        {{2,3}}
                        {{1},{2}}
                        {{1,2,3}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1},{2,3}}
                        {{2},{1,3}}
                        {{3},{1,2}}
                        {{1},{2},{3}}
                        {{1,2},{1,3},{2,3}}

Antichains are A000372.
The covering case is A319639.
The non-isomorphic multiset partition version is A319721.
The BII-numbers of these set-systems are the intersection of A326910 and A326853.
Set-systems whose dual is a weak antichain are A326968.
The unlabeled version is A327018.
Cf. A006126, A318099, A293606, A326704, A326950, A327020, A327057.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
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]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

A341633 a(n) is the cardinality of the central rank of the free distributive lattice on n generators.

Original entry on oeis.org

1, 2, 4, 24, 621, 492288, 81203064840

Offset: 1

Bruno L. O. Andreotti, Feb 16 2021

Sequence for 2 <= n <= 5 is given in Church (1940); n = 1 obtained trivially from {} - {{}} - {{}, {1}}; n = 6 and n = 7 obtained from the triangle A269699.
a(n) is also provably the number of downward closed subsets of the powerset of {1,2,3,...,n} which have the cardinality 2^(n-1).
If FD(n) (the free distributive lattice on n generators) is rank unimodal for all n, then a(n) is the largest cardinality of any rank of FD(n).
If FD(n) is rank unimodal and Sperner for all n, then a(n) is the width of FD(n). (Consequences provable, antecedents are open questions - e.g., Stanley (1991))
This sequence is related (at least methodologically) to the n-th Dedekind number (A000372), which is obtained from the cardinality of FD(n).
a(n) is also the number of balanced monotone Boolean functions. - Aniruddha Biswas, Nov 22 2024

			a(4)=24 is obtained from the 24 downsets on the 8th and central rank of FD(4), each containing 8 members (enumeration is arbitrary):
   1  {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
   2  {{},{1},{2},{4},{1,2},{1,4},{2,4},{1,2,4}}
   3  {{},{1},{3},{4},{1,3},{1,4},{3,4},{1,3,4}}
   4  {{},{2},{3},{4},{2,3},{2,4},{3,4},{2,3,4}}
   5  {{},{1},{2},{3},{4},{1,2},{1,3},{2,3}}
   6  {{},{1},{2},{3},{4},{1,2},{1,4},{2,4}}
   7  {{},{1},{2},{3},{4},{1,3},{1,4},{3,4}}
   8  {{},{1},{2},{3},{4},{2,3},{2,4},{3,4}}
   9  {{},{1},{2},{3},{4},{1,2},{1,3},{1,4}}
  10  {{},{1},{2},{3},{4},{1,2},{2,3},{2,4}}
  11  {{},{1},{2},{3},{4},{1,3},{2,3},{3,4}}
  12  {{},{1},{2},{3},{4},{1,4},{2,4},{3,4}}
  13  {{},{1},{2},{3},{4},{1,2},{2,3},{3,4}}
  14  {{},{1},{2},{3},{4},{1,2},{1,4},{3,4}}
  15  {{},{1},{2},{3},{4},{1,2},{1,4},{2,3}}
  16  {{},{1},{2},{3},{4},{1,2},{1,3},{3,4}}
  17  {{},{1},{2},{3},{4},{1,2},{2,4},{3,4}}
  18  {{},{1},{2},{3},{4},{1,2},{1,3},{2,4}}
  19  {{},{1},{2},{3},{4},{1,3},{1,4},{2,3}}
  20  {{},{1},{2},{3},{4},{1,3},{1,4},{2,4}}
  21  {{},{1},{2},{3},{4},{1,3},{2,4},{3,4}}
  22  {{},{1},{2},{3},{4},{1,3},{2,3},{2,4}}
  23  {{},{1},{2},{3},{4},{1,4},{2,3},{3,4}}
  24  {{},{1},{2},{3},{4},{1,4},{2,3},{2,4}}

Bruno L. O. Andreotti, Python program for n = 1 to 6
Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
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. 3, 11-12.
Randolph Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940). 732--734.
Randolph Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940). 732--734.
Richard P. Stanley, Some application of algebra to combinatorics, Discrete Applied Mathematics, 34 (1991), 241-277.

Cf. A000372, A269699, A371722.

Python
```
# See Andreotti link.
```

a(n) = A269699(n, 2^(n-1)).

A006360 Antichains (or order ideals) in the poset 223n or size of the distributive lattice J(223n).

Original entry on oeis.org

1, 50, 887, 8790, 59542, 307960, 1301610, 4701698, 14975675, 43025762, 113414717, 277904900, 639562508, 1393844960, 2896063220, 5768600412, 11066514565, 20526933442, 36936277875, 64660182026, 110394412610

Offset: 0

N. J. A. Sloane

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
Manfred Goebel, Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 9.
Index entries for sequences related to posets.

Cf. A000217, A000330, A050446, A050447, A006356, A006357, A006358, A006359, A000372, A056932, A006361, A006362, A056933, A056934, A056935, A056936, A056937.

Empirical G.f.: (x+1)*(x^6+36*x^5+279*x^4+594*x^3+279*x^2+36*x+1)/(1-x)^13. - Colin Barker, May 29 2012

More terms from Mitch Harris, Jul 16 2000

A006361 Antichains (or order ideals) in the poset 224n or size of the distributive lattice J(224n).

Original entry on oeis.org

1, 105, 3490, 59542, 650644, 5157098, 32046856, 164489084, 723509159, 2801747767, 9748942554, 30967306114, 90930233726, 249319296218, 643622467414, 1575086681342, 3675063064675, 8215220917795

Offset: 0

N. J. A. Sloane

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 9.
Index entries for sequences related to posets.

Cf. A000372, A056932, A006360, A006362, A056933, A056934, A056935, A056936, A056937.

Empirical G.f.: (x^10 +88*x^9 +1841*x^8 +13812*x^7 +44050*x^6 +64374*x^5 +44050*x^4 +13812*x^3 +1841*x^2 +88*x +1)/(1-x)^17. - Colin Barker, May 29 2012

More terms from Mitch Harris, Jul 16 2000

A006362 Antichains (or order ideals) in the poset 225n or size of the distributive lattice J(225n).

Original entry on oeis.org

1, 196, 11196, 307960, 5157098, 60112692, 530962446, 3764727340, 22326282261, 114158490576, 515063238810, 2087929609236, 7714649716552, 26285397502428, 83379798088110, 248202756212336, 697998155989501, 1864955619299196

Offset: 0

N. J. A. Sloane

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Index entries for sequences related to posets.

Cf. A000372, A056932, A006360, A006361, A056933, A056934, A056935, A056936, A056937.

More terms from Mitch Harris, Jul 16 2000

A056933 Antichains (or order ideals) in the poset 226n or size of the distributive lattice J(226n).

Original entry on oeis.org

1, 336, 30900, 1301610, 32046856, 530962446, 6479344016, 61951251333, 485198553532, 3217462615688, 18528857431906, 94529315562186, 434088353496446, 1817613939845670, 7014049051387480, 25167786776727516

Offset: 0

Mitch Harris

Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), p. 103-124

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
Index entries for sequences related to posets

Cf. A000372, A006360, A006361, A006362, A056932, A056934, A056935, A056936, A056937.

A056934 Antichains (or order ideals) in the poset 227n or size of the distributive lattice J(227n).

Original entry on oeis.org

1, 540, 75966, 4701698, 164489084, 3764727340, 61951251333, 782318812002, 7946895019096, 67270102239520, 487605585591870, 3092040981805272, 17451258588313354, 88902214572208640, 413569247116248032

Offset: 0

Mitch Harris

Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), p. 103-124

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
Index entries for sequences related to posets

Cf. A000372, A006360, A006361, A006362, A056932, A056933, A056935, A056936, A056937.

cp's OEIS Frontend

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326360 Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A327057 Number of antichains covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327062 Number of antichains of distinct sets covering a subset of {1..n} whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A341633 a(n) is the cardinality of the central rank of the free distributive lattice on n generators.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A006360 Antichains (or order ideals) in the poset 2*2*3*n or size of the distributive lattice J(2*2*3*n).

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A006361 Antichains (or order ideals) in the poset 2*2*4*n or size of the distributive lattice J(2*2*4*n).

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A006362 Antichains (or order ideals) in the poset 2*2*5*n or size of the distributive lattice J(2*2*5*n).

Views

Author

Keywords

References

A006360 Antichains (or order ideals) in the poset 223n or size of the distributive lattice J(223n).

A006361 Antichains (or order ideals) in the poset 224n or size of the distributive lattice J(224n).

A006362 Antichains (or order ideals) in the poset 225n or size of the distributive lattice J(225n).

A056933 Antichains (or order ideals) in the poset 226n or size of the distributive lattice J(226n).

A056934 Antichains (or order ideals) in the poset 227n or size of the distributive lattice J(227n).