A319639 -id:A319639 - cp's OEIS frontend

A326979 BII-numbers of T_1 set-systems.

0, 1, 2, 3, 7, 8, 9, 10, 11, 15, 25, 27, 30, 31, 42, 43, 45, 47, 51, 52, 53, 54, 55, 59, 60, 61, 62, 63, 75, 79, 91, 94, 95, 107, 109, 111, 115, 116, 117, 118, 119, 123, 124, 125, 126, 127, 128, 129, 130, 131, 135, 136, 137, 138, 139, 143, 153, 155, 158, 159

Offset: 1

Gus Wiseman, Aug 13 2019

nonn

A set-system is a finite set of finite nonempty sets. 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}}. The T_1 condition means that the dual is a (strict) antichain, meaning that none of its edges is a subset of any other.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of all T_1 set-systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  15: {{1},{2},{1,2},{3}}
  25: {{1},{3},{1,3}}
  27: {{1},{2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  42: {{2},{3},{2,3}}
  43: {{1},{2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  47: {{1},{2},{1,2},{3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}

BII-numbers of T_0 set-systems are A326947.
T_1 set-systems are counted by A326965, A326961 (covering), A326972 (unlabeled), and A326974 (unlabeled covering).
BII-numbers of set-systems whose dual is a weak antichain are A326966.
Cf. A059201, A059523, A319639, A326970, A326973, A326976, A326977.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],UnsameQ@@dual[bpe/@bpe[#]]&&stableQ[dual[bpe/@bpe[#]],SubsetQ]&]

A326966 BII-numbers of set-systems whose dual is a weak antichain.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 15, 16, 18, 25, 27, 30, 31, 32, 33, 42, 43, 45, 47, 51, 52, 53, 54, 55, 59, 60, 61, 62, 63, 64, 75, 76, 79, 82, 91, 94, 95, 97, 107, 109, 111, 115, 116, 117, 118, 119, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 135

Offset: 1

Gus Wiseman, Aug 13 2019

nonn

A set-system is a finite set of finite nonempty sets. 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.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of all set-systems whose dual is a weak antichain together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  16: {{1,3}}
  18: {{2},{1,3}}
  25: {{1},{3},{1,3}}
  27: {{1},{2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  32: {{2,3}}
  33: {{1},{2,3}}

Set-systems whose dual is a weak antichain are counted by A326968, with covering case A326970, unlabeled version A326971, and unlabeled covering version A326973.
BII-numbers of set-systems whose dual is strict (T_0) are A326947.
BII-numbers of set-systems whose dual is a (strict) antichain (T_1) are A326979.
Cf. A059523, A319639, A326961, A326965, A326969, A326974, A326975, A326978.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],stableQ[dual[bpe/@bpe[#]],SubsetQ]&]

A327020 Number of antichains covering n vertices where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 1, 2, 17, 1451, 3741198

Offset: 0

Gus Wiseman, Aug 17 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 with union {1..n} whose dual is pairwise intersecting.

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

Covering, intersecting antichains are A305844.
Covering, T1 antichains are A319639.
Cointersecting set-systems are A327039.
Covering, cointersecting set-systems are A327040.
Covering, cointersecting set-systems are A327051.
The non-covering version is A327057.
Covering, intersecting, T1 set-systems are A327058.
Unlabeled cointersecting antichains of multisets are A327060.
Cf. A003465, A305843, A319765, A326853, A327037, A327038, A327053.

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],Union@@#==Range[n]&&stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,4}]

Inverse binomial transform of A327057.

A304996 Number of unlabeled antichains of finite sets spanning up to n vertices with singleton edges allowed.

Original entry on oeis.org

1, 2, 6, 24, 166, 3266, 826308

Offset: 0

Gus Wiseman, May 23 2018

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

Partial sums of A304997.
Cf. A006126, A261005, A304997, A304998, A304999, A305000, A305001.
Cf. A000372, A014466, A293993, A319639, A319721, A326704, A326972.

a(5)-a(6) from Andrew Howroyd, Aug 14 2019

A326975 Number of factorizations of n into factors > 1 whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 2, 1, 2, 2, 5, 1, 2, 1, 2, 2, 2, 1, 3, 2, 2, 3, 2, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 3, 1, 5, 1, 2, 2, 2, 1, 5, 2, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 4, 1, 2, 2, 11, 2, 5, 1, 2, 2, 5, 1, 12, 1, 2, 2, 2, 2, 5, 1, 5, 5, 2, 1, 4, 2, 2

Offset: 1

Gus Wiseman, Aug 13 2019

nonn

The dual of a multiset system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The dual of a factorization is the dual of the multiset partition obtained by replacing each factor with its multiset of prime indices.

A weak antichain is a multiset of multisets, none of which is a proper submultiset of any other.

			The a(36) = 9 factorizations:
  (36)
  (4*9)
  (6*6)
  (2*18)
  (3*12)
  (2*2*9)
  (2*3*6)
  (3*3*4)
  (2*2*3*3)

The T_0 case (where the dual is strict) is A316978.
Set-systems whose dual is a weak antichain are A326968.
Partitions whose dual is a weak antichain are A326978.
The T_1 case (where the dual is a strict antichain) is A327012.
Cf. A001055, A059523, A316978, A319639, A326965, A326966, A326969, A326970, A326971, A326976, A326977.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[facs[n],stableQ[dual[primeMS/@#],submultQ]&]],{n,100}]

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

Original entry on oeis.org

2, 2, 4, 72, 38040, 4020463392, 18438434825136728352, 340282363593610211921722192165556850240, 115792089237316195072053288318104625954343609704705784618785209431974668731584

Offset: 0

Gus Wiseman, Aug 13 2019

nonn

Same as A059052 except with a(1) = 2 instead of 4.
The dual of a set of subsets 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 subsets where no edge is a subset of any other.
Alternatively, these are sets of subsets of {1..n} covering all n vertices where every vertex is the unique common element of some subset of the edges.

			The a(0) = 2 through a(2) = 4 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Covering sets of subsets are A000371.
Covering T_0 sets of subsets are A326939.
The case without empty edges is A326961.
The non-covering version is A326967.
Cf. A003181, A059052, A059523, A319639, A326951, A326965, A326974, A326976, A326977, A326979.

Table[Length[Select[Subsets[Subsets[Range[n]]],Length[Union[Select[Intersection@@@Rest[Subsets[#]],Length[#]==1&]]]==n&]],{n,0,3}]

Binomial transform of A326967.

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}]

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

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 9, 5, 2, 0, 114, 84, 44, 17, 0, 6894, 6348, 4983, 3141, 1451, 0, 7785062

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
     9    5    2    0
   114   84   44   17    0
  6894 6348 4983 3141 1451    0
The antichains counted in row n = 3:
  {123}         {123}         {123}
  {1}{23}       {12}{13}      {12}{13}{23}
  {2}{13}       {12}{23}
  {3}{12}       {13}{23}
  {12}{13}      {12}{13}{23}
  {12}{23}
  {13}{23}
  {1}{2}{3}
  {12}{13}{23}

Column k = 0 is A307249, or A006126 if empty edges are allowed.
Column k = 1 is A048143 (clutters), if we assume A048143(0) = A048143(1) = 0.
Column k = 2 is A275307 (blobs), if we assume A275307(1) = A275307(2) = 0.
Column k = n - 1 is A327020 (cointersecting antichains).
The unlabeled version is A327358.
Negated first differences of rows are A327351.
BII-numbers of antichains are A326704.
Antichain covers are A006126.
Cf. A003465, A014466, A120338, A293606, A293993, A319639, A323818, A327112, A327125, A327334, A327336, A327352, A327356, A327357, A327358.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
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]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Union@@#==Range[n]&&vertConnSys[Range[n],#]>=k&]],{n,0,4},{k,0,n}]

a(21) from Robert Price, May 24 2021

A327058 Number of pairwise intersecting set-systems covering n vertices whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 1, 3, 155

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) = 3 set-systems:
  {}  {{1}}  {{12}}  {{123}}
                     {{12}{13}{23}}
                     {{12}{13}{23}{123}}

Covering intersecting set-systems are A305843.
The BII-numbers of these set-systems are the intersection of A326910 and A326966.
Covering coantichains are A326970.
The non-covering version is A327059.
The unlabeled multiset partition version is A327060.
Cf. A006126, A051185, A059523, A305844, A319639, A326961, A326965, A326968, 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}],Intersection[#1,#2]=={}&],Union@@#==Range[n]&&stableQ[dual[#],SubsetQ]&]],{n,0,3}]

Inverse binomial transform of A327059.

A327425 Number of unlabeled antichains of nonempty sets covering n vertices where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 1, 2, 6, 54

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.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 6 antichains:
    {1}  {12}  {123}         {1234}
               {12}{13}{23}  {12}{134}{234}
                             {124}{134}{234}
                             {12}{13}{14}{234}
                             {123}{124}{134}{234}
                             {12}{13}{14}{23}{24}{34}

The labeled version is A327020.
Unlabeled covering antichains are A261005.
The weighted version is A327060.
Cf. A006126, A014466, A055621, A293606, A293993, A305844, A307249, A319639, A326704, A327057, A327058, A327358, A327359.

cp's OEIS Frontend

A326979 BII-numbers of T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326966 BII-numbers of set-systems whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327020 Number of antichains covering n vertices where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A304996 Number of unlabeled antichains of finite sets spanning up to n vertices with singleton edges allowed.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A326975 Number of factorizations of n into factors > 1 whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326960 Number of sets of subsets of {1..n} covering all n vertices whose dual is a (strict) antichain, also called covering T_1 sets of subsets.

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A327058 Number of pairwise intersecting set-systems covering n vertices whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples