A014466 -id:A014466 - cp's OEIS frontend

A302251 The number of nonempty antichains in the lattice of set partitions.

1, 2, 9, 346, 79814831

Offset: 1

John Machacek, Apr 04 2018

Computing terms in this sequence is analogous to Dedekind's problem which asks for the number of antichains in the Boolean algebra.

This count excludes the empty antichain consisting of no set partitions.

			For n = 3 the a(3) = 9 nonempty antichains are:
{1/2/3}
{1/23}
{12/3}
{13/2}
{1/23, 12/3}
{1/23, 13/2}
{12/3, 13/2}
{1/23, 12/3, 13/2}
{123}
Here we have used the usual shorthand notation for set partitions where 1/23 denotes {{1}, {2,3}}.

Sebastian Bozlee, Bob Kuo, and Adrian Neff, A classification of modular compactifications of the space of pointed elliptic curves by Gorenstein curves, arXiv:2105.10582 [math.AG], 2021.

Equals A302250 - 1, Cf. A000372, A007153, A003182, A014466.

[Posets.SetPartitions(n).antichains().cardinality() - 1 for n in range(4)]
# minus removes the empty antichain

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

Original entry on oeis.org

2, 2, 2, 3, 29, 1961, 1379274, 229755337550, 423295079757497714060

Offset: 0

Gus Wiseman, Jul 03 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(4) = 29 antichains:
  {}
  {{}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,4},{2,4}}
  {{1,3},{1,4},{3,4}}
  {{2,3},{2,4},{3,4}}
  {{1,2},{1,3},{2,3,4}}
  {{1,2},{1,4},{2,3,4}}
  {{1,2},{2,3},{1,3,4}}
  {{1,2},{2,4},{1,3,4}}
  {{1,3},{1,4},{2,3,4}}
  {{1,3},{2,3},{1,2,4}}
  {{1,3},{3,4},{1,2,4}}
  {{1,4},{2,4},{1,2,3}}
  {{1,4},{3,4},{1,2,3}}
  {{2,3},{2,4},{1,3,4}}
  {{2,3},{3,4},{1,2,4}}
  {{2,4},{3,4},{1,2,3}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,2,4},{2,3,4}}
  {{1,4},{1,2,3},{2,3,4}}
  {{2,3},{1,2,4},{1,3,4}}
  {{2,4},{1,2,3},{1,3,4}}
  {{3,4},{1,2,3},{1,2,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2},{2,3},{2,4},{1,3,4}}
  {{1,3},{2,3},{3,4},{1,2,4}}
  {{1,4},{2,4},{3,4},{1,2,3}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

The case without empty edges is A326366.
Intersecting antichains are A326372.
Antichains of nonempty sets with empty intersection are A006126 or A307249.
Cf. A001206, A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326363, A326365, A326373.

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

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

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

A327807 Triangle read by rows where T(n,k) is the number of unlabeled antichains of sets with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 9, 3, 2, 0, 29, 14, 10, 6, 0, 209, 157, 128, 91, 54, 0

Offset: 0

Gus Wiseman, Sep 26 2019

An antichain is a set of sets, none of which is a subset of any other.

The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

			Triangle begins:
    1
    2   0
    4   1   0
    9   3   2   0
   29  14  10   6   0
  209 157 128  91  54   0

Column k = 0 is A306505.
Column k = 1 is A261006 (clutters), if we assume A261006(0) = A261006(1) = 0.
Column k = 2 is A305028 (blobs), if we assume A305028(0) = A305028(2) = 0.
Except for the first column, same as A327358 (the covering case).
The labeled version is A327806.
Cf. A014466, A293606, A326704, A326950, A327062, A327334, A327350, A327351, A327805, A327808.

A174537 Partial sums of A000372.

Original entry on oeis.org

2, 5, 11, 31, 199, 7780, 7836134, 2414689877132, 56130437231102247784920, 286386577668298411184599588898700746597286

Offset: 0

Jonathan Vos Post, Mar 21 2010

nonn

Partial sums of Dedekind numbers. Partial sums of number of monotone Boolean functions of n variables (increasing functions from P(S), the set of subsets of S, to {0,1}). Partial sums of number of antichains of subsets of an n-set. The subsequence of primes in this partial sum begins: 2, 5, 11, 31, 199 is prime (5 in a row, then no more known).

			a(4) = 2 + 3 + 6 + 20 + 168 = 199 is prime.

Cf. A000372, A014466, A007153, A003182, A059119.

a(n) = Sum_{i=0..n} A000372(i) = Sum_{i=0..n} (A014466(i) + 1) = Sum_{i=0..n} (A007153(i) + 2).

a(9) from A000372 - Dmitry I. Ignatov, Nov 27 2023

cp's OEIS Frontend

A302251 The number of nonempty antichains in the lattice of set partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327807 Triangle read by rows where T(n,k) is the number of unlabeled antichains of sets with n vertices and vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A174537 Partial sums of A000372.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions