A261005 -id:A261005 - 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

A304999 Number of labeled antichains of finite sets spanning n vertices with singleton edges allowed.

Original entry on oeis.org

1, 1, 5, 53, 1577, 212137, 496946349, 309068823607069, 14369391923126237496803793, 146629927766168786109802623629262590838145873

Offset: 0

Gus Wiseman, May 23 2018

Only the non-singleton edges are required to form an antichain.

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

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 p. 4.
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Cf. A006126, A014466, A261005, A304996, A304997, A304998, A304999, A305000, A305001.

Cf. A000372, A003182, A304985, A305844, A306505, A319721, A321679, A324167.

Exponential transform of A304985.

Inverse binomial transform of A305000. - Aniruddha Biswas, May 12 2024

a(5)-a(8) from Gus Wiseman, May 31 2018

a(9) from Aniruddha Biswas, May 12 2024

A327426 Number of non-connected, unlabeled, antichain covers of {1..n} (vertex-connectivity 0).

Original entry on oeis.org

1, 1, 1, 2, 6, 23, 201, 16345

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices. A singleton is not considered connected.

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.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 23 antichains:
    {1}{2}  {1}{23}    {1}{234}         {1}{2345}
            {1}{2}{3}  {12}{34}         {12}{345}
                       {1}{2}{34}       {1}{2}{345}
                       {1}{24}{34}      {1}{23}{45}
                       {1}{2}{3}{4}     {12}{35}{45}
                       {1}{23}{24}{34}  {1}{25}{345}
                                        {1}{2}{3}{45}
                                        {1}{245}{345}
                                        {1}{2}{35}{45}
                                        {1}{2}{3}{4}{5}
                                        {1}{24}{35}{45}
                                        {1}{25}{35}{45}
                                        {12}{34}{35}{45}
                                        {1}{24}{25}{345}
                                        {1}{23}{245}{345}
                                        {1}{2}{34}{35}{45}
                                        {1}{235}{245}{345}
                                        {1}{23}{24}{35}{45}
                                        {1}{25}{34}{35}{45}
                                        {1}{23}{24}{25}{345}
                                        {1}{234}{235}{245}{345}
                                        {1}{24}{25}{34}{35}{45}
                                        {1}{23}{24}{25}{34}{35}{45}

Column k = 0 of A327359.
The labeled version is A120338.
The non-covering version is A327424 (partial sums).
Cf. A014466, A261005, A327354, A327355, A327437.

a(n > 1) = A261005(n) - A261006(n).

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

A320353 Number of antichains of multisets whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 1, 3, 5, 11, 17, 36, 56, 107, 175, 311, 505, 887

Offset: 0

Gus Wiseman, Oct 11 2018

			The a(1) = 1 through a(5) = 17 antichains:
  {{1}}  {{2}}      {{3}}          {{4}}              {{5}}
         {{1,1}}    {{1,2}}        {{1,3}}            {{1,4}}
         {{1},{1}}  {{1,1,1}}      {{2,2}}            {{2,3}}
                    {{1},{2}}      {{1,1,2}}          {{1,1,3}}
                    {{1},{1},{1}}  {{1},{3}}          {{1,2,2}}
                                   {{2},{2}}          {{1},{4}}
                                   {{1,1,1,1}}        {{2},{3}}
                                   {{2},{1,1}}        {{1,1,1,2}}
                                   {{1,1},{1,1}}      {{1},{2,2}}
                                   {{1},{1},{2}}      {{3},{1,1}}
                                   {{1},{1},{1},{1}}  {{1,1,1,1,1}}
                                                      {{1,1},{1,2}}
                                                      {{1},{1},{3}}
                                                      {{1},{2},{2}}
                                                      {{2},{1,1,1}}
                                                      {{1},{1},{1},{2}}
                                                      {{1},{1},{1},{1},{1}}

Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, Journal of Integer Sequences, Vol. 7 (2004).

Cf. A001970, A006126, A050342, A089259, A258466, A261005, A261049, A293994, A319719, A319721, A320328, A320355, A320356.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
antiQ[s_]:=Select[Tuples[s,2],And[UnsameQ@@#,submultisetQ@@#]&]=={};
Table[Length[Select[Join@@mps/@IntegerPartitions[n],antiQ]],{n,8}]

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

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 5, 3, 2, 0, 20, 14, 10, 6, 0, 180, 157, 128, 91, 54, 0

Offset: 0

Gus Wiseman, Sep 09 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.
The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

			Triangle begins:
    1
    1   0
    2   1   0
    5   3   2   0
   20  14  10   6   0
  180 157 128  91  54   0
Non-isomorphic representatives of the antichains counted in row n = 4:
  {1234}          {1234}           {1234}           {1234}
  {1}{234}        {12}{134}        {123}{124}       {12}{134}{234}
  {12}{34}        {123}{124}       {12}{13}{234}    {123}{124}{134}
  {12}{134}       {12}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {123}{124}      {12}{13}{24}     {123}{124}{134}  {123}{124}{134}{234}
  {1}{2}{34}      {12}{13}{234}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {2}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {12}{13}{14}    {123}{124}{134}  {12}{13}{14}{23}{24}
  {12}{13}{24}    {12}{13}{14}{23} {123}{124}{134}{234}
  {1}{2}{3}{4}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {12}{13}{234}   {12}{13}{14}{234}
  {12}{134}{234}  {12}{13}{14}{23}{24}
  {123}{124}{134} {123}{124}{134}{234}
  {4}{12}{13}{23} {12}{13}{14}{23}{24}{34}
  {12}{13}{14}{23}
  {12}{13}{24}{34}
  {12}{13}{14}{234}
  {12}{13}{14}{23}{24}
  {123}{124}{134}{234}
  {12}{13}{14}{23}{24}{34}

Column k = 0 is A261005, or A006602 if empty edges are allowed.
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.
Column k = n - 1 is A327425 (cointersecting).
The labeled version is A327350.
Negated first differences of rows are A327359.
Cf. A006126, A055621, A120338, A293606, A293993, A327334, A327351, A327356.

A327359 Triangle read by rows where T(n,k) is the number of unlabeled antichains of nonempty sets covering n vertices with vertex-connectivity exactly k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 1, 2, 0, 6, 4, 4, 6, 0, 23, 29, 37, 37, 54, 0

Offset: 0

Gus Wiseman, Sep 10 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.
The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

			Triangle begins:
   1
   1  0
   1  1  0
   2  1  2  0
   6  4  4  6  0
  23 29 37 37 54  0
Row n = 4 counts the following antichains:
{1}{234}      {14}{234}        {134}{234}           {1234}
{12}{34}      {13}{24}{34}     {13}{14}{234}        {12}{134}{234}
{1}{2}{34}    {14}{24}{34}     {12}{13}{24}{34}     {124}{134}{234}
{1}{24}{34}   {14}{23}{24}{34} {13}{14}{23}{24}{34} {12}{13}{14}{234}
{1}{2}{3}{4}                                        {123}{124}{134}{234}
{1}{23}{24}{34}                                     {12}{13}{14}{23}{24}{34}

Row sums are A261005, or A006602 if empty edges are allowed.
Column k = 0 is A327426.
Column k = 1 is A327436.
Column k = n - 1 is A327425.
The labeled version is A327351.
Cf. A003465, A006126, A014466, A048143, A293993, A323818, A326704, A327125, A327334, A327336, A327350, A327358.

A327437 Number of unlabeled antichains of nonempty subsets of {1..n} that are either non-connected or non-covering (spanning edge-connectivity 0).

Original entry on oeis.org

1, 1, 3, 6, 15, 52, 410, 32697

Offset: 0

Gus Wiseman, Sep 11 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.

The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices.

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

Column k = 0 of A327438.
The labeled version is A327355.
The covering case is A327426.
Cf. A014466 A052446, A120338, A261005, A293606, A327201, A327236, A327352, A327353, A327354, A327438.

a(n > 0) = A306505(n) - A261006(n).

A306550 Array read by antidiagonals where A(n,k) is the number of labeled k-antichains covering n vertices.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 6, 0, 0, 0, 0, 1, 25, 2, 0, 0, 0, 0, 1, 90, 56, 0, 0, 0, 0, 0, 1, 301, 790, 25, 0, 0, 0, 0, 0, 1, 966, 8380, 1895, 6, 0, 0, 0, 0, 0, 1, 3025, 76482, 70370, 2116, 1, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 23 2019

			Array begins:
    n=0: n=1: n=2: n=3: n=4: n=5:
---------------------------------
k=0:  1    0    0    0    0    0
k=1:  1    1    1    1    1    1
k=2:  0    0    1    6   25   90
k=3:  0    0    0    2   56  790
k=4:  0    0    0    0   25 1895
k=5:  0    0    0    0    6 2116
Column n = 3 counts the following antichains:
  {{123}}  {{1}{23}}   {{1}{2}{3}}
           {{2}{13}}   {{12}{13}{23}}
           {{3}{12}}
           {{12}{13}}
           {{12}{23}}
           {{13}{23}}

Column sums are A006126. Row k = 2 is A000392. Rows k = 3-9 are A056046-A056049, A056052, A056101, A056104.

Cf. A000372, A006126, A006602, A014466, A261005, A305000, A305844, A317674.

nn=8;
stableSets[u_,Q_,k_]:=If[k==0,{{}},If[Length[u]==0,{},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q,k],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q,k-1]]]]];
ae[n_,k_]:=Length[Select[stableSets[Subsets[Range[n]],SubsetQ,k],Union@@#==Range[n]&]];
Table[ae[k,n-k],{n,0,nn},{k,0,n}]

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

A304999 Number of labeled antichains of finite sets spanning n vertices with singleton edges allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A327426 Number of non-connected, unlabeled, antichain covers of {1..n} (vertex-connectivity 0).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A320353 Number of antichains of multisets whose multiset union is an integer partition of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

A327359 Triangle read by rows where T(n,k) is the number of unlabeled antichains of nonempty sets covering n vertices with vertex-connectivity exactly k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327437 Number of unlabeled antichains of nonempty subsets of {1..n} that are either non-connected or non-covering (spanning edge-connectivity 0).

Views

Author