A305844 -id:A305844 - cp's OEIS frontend

A326365 Number of intersecting antichains with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

1, 0, 0, 1, 23, 1834, 1367903, 229745722873, 423295077919493525420

Offset: 0

Gus Wiseman, Jul 01 2019

Covering means there are no isolated vertices. A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.

			The a(4) = 23 intersecting antichains with empty intersection:
  {{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}}

Intersecting antichain covers are A305844.
Intersecting covers with empty intersection are A326364.
Antichain covers with empty intersection are A305001.
The binomial transform is the non-covering case A326366.
Covering, intersecting antichains with empty intersection are A326365.
Cf. A006126, A007363, A014466, A051185, A058891, A305843, A307249, A318128, A318129, 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]]]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&],And[Union@@#==Range[n],#=={}||Intersection@@#=={}]&]],{n,0,4}]

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

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

Original entry on oeis.org

1, 1, 1, 2, 28, 1960, 1379273, 229755337549, 423295079757497714059

Offset: 0

Gus Wiseman, Jul 01 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(0) = 1 through a(4) = 28 intersecting antichains with empty intersection:
  {}  {}  {}  {}              {}
              {{12}{13}{23}}  {{12}{13}{23}}
                              {{12}{14}{24}}
                              {{13}{14}{34}}
                              {{23}{24}{34}}
                              {{12}{13}{234}}
                              {{12}{14}{234}}
                              {{12}{23}{134}}
                              {{12}{24}{134}}
                              {{13}{14}{234}}
                              {{13}{23}{124}}
                              {{13}{34}{124}}
                              {{14}{24}{123}}
                              {{14}{34}{123}}
                              {{23}{24}{134}}
                              {{23}{34}{124}}
                              {{24}{34}{123}}
                              {{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}}

The case with empty edges allowed is A326375.
Intersecting antichains of nonempty sets are A001206.
Intersecting set systems with empty intersection are A326373.
Antichains of nonempty sets with empty intersection are A006126 or A307249.
The inverse binomial transform is the covering case A326365.
Cf. A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326361, A326362, A326363, A326364.

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

a(n) = A326375(n) - 1.

a(n) = A001206(n+1) + A307249(n) - A014466(n). - Andrew Howroyd, Aug 14 2019

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

A336737 Number of factorizations of n whose factors have pairwise intersecting prime signatures.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 2, 3, 1, 5, 1, 2, 2, 2, 2, 7, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 6, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 4, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 6, 3, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Aug 06 2020

nonn

First differs from A327400 at a(72) = 9, A327400(72) = 10.

A number's prime signature (row n of A124010) is the sequence of positive exponents in its prime factorization.

			The a(n) factorizations for n = 2, 4, 12, 24, 30, 36, 60:
  (2)  (4)    (12)     (24)       (30)     (36)       (60)
       (2*2)  (2*6)    (2*12)     (5*6)    (4*9)      (2*30)
              (2*2*3)  (2*2*6)    (2*15)   (6*6)      (3*20)
                       (2*2*2*3)  (3*10)   (2*18)     (5*12)
                                  (2*3*5)  (3*12)     (6*10)
                                           (2*3*6)    (2*5*6)
                                           (2*2*3*3)  (2*2*15)
                                                      (2*3*10)
                                                      (2*2*3*5)

A001055 counts factorizations.
A118914 is sorted prime signature.
A124010 is prime signature.
A336736 counts factorizations with disjoint signatures.
Cf. A003182, A051185, A305843, A305844, A305854, A306006, A319752, A319787, A319789, A321469, A336424.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
prisig[n_]:=If[n==1,{},Last/@FactorInteger[n]];
Table[Length[Select[facs[n],stableQ[#,Intersection[prisig[#1],prisig[#2]]=={}&]&]],{n,100}]

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

A326364 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

Original entry on oeis.org

1, 0, 0, 2, 426, 987404, 887044205940, 291072121051815578010398, 14704019422368226413234332571239460300433492086, 12553242487939461785560846872353486129110194397301168776798213375239447299205732561174066488

Offset: 0

Gus Wiseman, Jul 01 2019

nonn

Covering means there are no isolated vertices. A set system (set of sets) is intersecting if no two edges are disjoint.

			The a(3) = 2 intersecting set systems with empty intersection:
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Covering set systems with empty intersection are A318128.
Covering, intersecting set systems are A305843.
Covering, intersecting antichains with empty intersection are A326365.
Cf. A006126, A007363, A014466, A051185, A058891, A305844, A307249, A318129, 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]]]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],Intersection[#1,#2]=={}&],And[Union@@#==Range[n],#=={}||Intersection@@#=={}]&]],{n,0,4}]

Inverse binomial transform of A326373. - Andrew Howroyd, Aug 12 2019

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

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.

A327060 Number of non-isomorphic weight-n weak antichains of multisets where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 3, 4, 9, 11, 30, 42, 103, 194, 443

Offset: 0

Gus Wiseman, Aug 18 2019

A multiset partition is a finite multiset of finite nonempty multisets. It is a weak antichain if no part is a proper submultiset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 multiset partitions:
  {}  {{1}}  {{11}}    {{111}}      {{1111}}        {{11111}}
             {{12}}    {{122}}      {{1122}}        {{11222}}
             {{1}{1}}  {{123}}      {{1222}}        {{12222}}
                       {{1}{1}{1}}  {{1233}}        {{12233}}
                                    {{1234}}        {{12333}}
                                    {{11}{11}}      {{12344}}
                                    {{12}{12}}      {{12345}}
                                    {{12}{22}}      {{11}{122}}
                                    {{1}{1}{1}{1}}  {{12}{222}}
                                                    {{33}{123}}
                                                    {{1}{1}{1}{1}{1}}

Antichains are A000372.
The BII-numbers of these set-systems are the intersection of A326853 and A326704.
Cointersecting set-systems are A327039.
The set-system version is A327057, with covering case A327058.
Cf. A006126, A007716, A051185, A305844, A326965, A327020, A327059, A327062.

A329561 BII-numbers of intersecting antichains of sets.

Original entry on oeis.org

0, 1, 2, 4, 8, 16, 20, 32, 36, 48, 52, 64, 128, 256, 260, 272, 276, 320, 512, 516, 544, 548, 576, 768, 772, 832, 1024, 1040, 1056, 1072, 1088, 2048, 2064, 2080, 2096, 2112, 2304, 2320, 2368, 2560, 2592, 2624, 2816, 2880, 3072, 3088, 3104, 3120, 3136, 4096

Offset: 1

Gus Wiseman, Nov 28 2019

nonn

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 set-system (finite set of finite nonempty sets of positive integers) 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.

A set-system is intersecting if no two edges are disjoint. It is an antichain if no edge is a proper subset of any other.

			The sequence of terms together with their corresponding set-systems begins:
    0: {}
    1: {{1}}
    2: {{2}}
    4: {{1,2}}
    8: {{3}}
   16: {{1,3}}
   20: {{1,2},{1,3}}
   32: {{2,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
   52: {{1,2},{1,3},{2,3}}
   64: {{1,2,3}}
  128: {{4}}
  256: {{1,4}}
  260: {{1,2},{1,4}}
  272: {{1,3},{1,4}}
  276: {{1,2},{1,3},{1,4}}
  320: {{1,2,3},{1,4}}
  512: {{2,4}}
  516: {{1,2},{2,4}}

Intersection of A326704 (antichains) and A326910 (intersecting).
Covering intersecting antichains of sets are counted by A305844.
BII-numbers of antichains with empty intersection are A329560.
Cf. A000120, A048143, A048793, A070939, A087086, A305857, A306007, A326031, A326361, A326912, A329628.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,1000],stableQ[bpe/@bpe[#],SubsetQ[#1,#2]||Intersection[#1,#2]=={}&]&]

A329628 Smallest BII-number of an intersecting antichain with n edges.

Original entry on oeis.org

0, 1, 20, 52, 2880, 275520

Offset: 0

Gus Wiseman, Nov 28 2019

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 set-system (finite set of finite nonempty sets of positive integers) 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. Elements of a set-system are sometimes called edges.

A set-system is intersecting if no two edges are disjoint. It is an antichain if no edge is a proper subset of any other.

			The sequence of terms together with their corresponding set-systems begins:
       0: {}
       1: {{1}}
      20: {{1,2},{1,3}}
      52: {{1,2},{1,3},{2,3}}
    2880: {{1,2,3},{1,4},{2,4},{3,4}}
  275520: {{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,5}}

The not necessarily intersecting version is A329626.
MM-numbers of intersecting antichains are A329366.
BII-numbers of antichains are A326704.
BII-numbers of intersecting set-systems are A326910.
BII-numbers of intersecting antichains are A329561.
Covering intersecting antichains of sets are A305844.
Non-isomorphic intersecting antichains of multisets are A306007.
Cf. A000120, A048793, A070939, A072639, A316476, A305857, A326031, A326361, A326912, A329560.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
First/@GatherBy[Select[Range[0,10000],stableQ[bpe/@bpe[#],SubsetQ[#1,#2]||Intersection[#1,#2]=={}&]&],Length[bpe[#]]&]

A305855 Number of unlabeled spanning intersecting antichains on n vertices.

Original entry on oeis.org

1, 1, 1, 3, 9, 72, 3441, 47170585

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. S is spanning if every vertex is contained in some edge.

			Non-isomorphic representatives of the a(4) = 9 spanning intersecting antichains:
  {{1,2,3,4}}
  {{1,4},{2,3,4}}
  {{1,3,4},{2,3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,4},{2,3,4}}
  {{1,4},{2,4},{3,4}}
  {{1,2,4},{1,3,4},{2,3,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Cf. A001206, A006126, A051185, A261006, A283877, A304998, A305843, A305844, A305854-A305857.

a(n) = A305857(n) - A305857(n-1) for n > 0. - Andrew Howroyd, Aug 13 2019

a(6) from Andrew Howroyd, Aug 13 2019

a(7) from Brendan McKay, May 11 2020

cp's OEIS Frontend

A326365 Number of intersecting antichains with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A326366 Number of intersecting antichains of nonempty 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

A336737 Number of factorizations of n whose factors have pairwise intersecting prime signatures.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326364 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327060 Number of non-isomorphic weight-n weak antichains of multisets where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

A329561 BII-numbers of intersecting antichains of sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329628 Smallest BII-number of an intersecting antichain with n edges.

Views

Author

Keywords