A326965 -id:A326965 - cp's OEIS frontend

A326961 Number of set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called covering T_1 set-systems.

1, 1, 2, 36, 19020, 2010231696, 9219217412568364176, 170141181796805105960861096082778425120, 57896044618658097536026644159052312977171804852352892309392604715987334365792

Offset: 0

Gus Wiseman, Aug 12 2019

nonn

Same as A059523 except with a(1) = 1 instead of 2.

Alternatively, these are set-systems covering n vertices whose dual is a (strict) antichain. 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. An antichain is a set of sets, none of which is a subset of any other.

			The a(3) = 36 set-systems:
  {{1}{2}{3}}        {{12}{13}{23}{123}}     {{2}{3}{12}{13}{23}}
  {{12}{13}{23}}     {{1}{2}{3}{12}{13}}     {{2}{3}{12}{13}{123}}
  {{1}{2}{3}{12}}    {{1}{2}{3}{12}{23}}     {{2}{12}{13}{23}{123}}
  {{1}{2}{3}{13}}    {{1}{2}{3}{13}{23}}     {{3}{12}{13}{23}{123}}
  {{1}{2}{3}{23}}    {{1}{2}{12}{13}{23}}    {{1}{2}{3}{12}{13}{23}}
  {{1}{2}{13}{23}}   {{1}{2}{3}{12}{123}}    {{1}{2}{3}{12}{13}{123}}
  {{1}{2}{3}{123}}   {{1}{2}{3}{13}{123}}    {{1}{2}{3}{12}{23}{123}}
  {{1}{3}{12}{23}}   {{1}{2}{3}{23}{123}}    {{1}{2}{3}{13}{23}{123}}
  {{2}{3}{12}{13}}   {{1}{3}{12}{13}{23}}    {{1}{2}{12}{13}{23}{123}}
  {{1}{12}{13}{23}}  {{1}{2}{13}{23}{123}}   {{1}{3}{12}{13}{23}{123}}
  {{2}{12}{13}{23}}  {{1}{3}{12}{23}{123}}   {{2}{3}{12}{13}{23}{123}}
  {{3}{12}{13}{23}}  {{1}{12}{13}{23}{123}}  {{1}{2}{3}{12}{13}{23}{123}}

Covering set-systems are A003465.
Covering T_0 set-systems are A059201.
The version with empty edges allowed is A326960.
The non-covering version is A326965.
Covering set-systems whose dual is a weak antichain are A326970.
The unlabeled version is A326974.
The BII-numbers of T_1 set-systems are A326979.
Cf. A058891, A059052, A059523, A323818, A326972, A326973, A326976, A326977.

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

Inverse binomial transform of A326965.

A326974 Number of unlabeled set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called unlabeled covering T_1 set-systems.

Original entry on oeis.org

1, 1, 2, 16, 1212

Offset: 0

Gus Wiseman, Aug 11 2019

Alternatively, these are unlabeled set-systems covering n vertices whose dual is a (strict) antichain. 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}}. An antichain is a set-system where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 16 set-systems:
  {}  {{1}}  {{1},{2}}        {{1},{2},{3}}
             {{1},{2},{1,2}}  {{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{2,3}}
                              {{1},{2},{1,3},{2,3}}
                              {{1},{2},{3},{1,2,3}}
                              {{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{1,3},{2,3}}
                              {{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3}}
                              {{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Unlabeled covers are A055621.
The same with T_0 instead of T_1 is A319637.
The labeled version is A326961.
The non-covering version is A326972 (partial sums).
Unlabeled covering set-systems whose dual is a weak antichain are A326973.
Cf. A000612, A059523, A319559, A326946, A326951, A326965, A326970, A326971, A326976, A326977, A326979.

a(n > 0) = A326972(n) - A326972(n - 1).

A326979 BII-numbers of T_1 set-systems.

Original entry on oeis.org

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

A326970 Number of set-systems covering n vertices whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 3, 43, 19251

Offset: 0

Gus Wiseman, Aug 10 2019

A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edges 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(3) = 43 set-systems:
  {123}  {1}{23}  {1}{2}{3}     {1}{2}{3}{12}
         {2}{13}  {12}{13}{23}  {1}{2}{3}{13}
         {3}{12}  {1}{23}{123}  {1}{2}{3}{23}
                  {2}{13}{123}  {1}{2}{13}{23}
                  {3}{12}{123}  {1}{2}{3}{123}
                                {1}{3}{12}{23}
                                {2}{3}{12}{13}
                                {1}{12}{13}{23}
                                {2}{12}{13}{23}
                                {3}{12}{13}{23}
                                {12}{13}{23}{123}
.
  {1}{2}{3}{12}{13}     {1}{2}{3}{12}{13}{23}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{3}{12}{23}     {1}{2}{3}{12}{13}{123}
  {1}{2}{3}{13}{23}     {1}{2}{3}{12}{23}{123}
  {1}{2}{12}{13}{23}    {1}{2}{3}{13}{23}{123}
  {1}{2}{3}{12}{123}    {1}{2}{12}{13}{23}{123}
  {1}{2}{3}{13}{123}    {1}{3}{12}{13}{23}{123}
  {1}{2}{3}{23}{123}    {2}{3}{12}{13}{23}{123}
  {1}{3}{12}{13}{23}
  {2}{3}{12}{13}{23}
  {1}{2}{13}{23}{123}
  {1}{3}{12}{23}{123}
  {2}{3}{12}{13}{123}
  {1}{12}{13}{23}{123}
  {2}{12}{13}{23}{123}
  {3}{12}{13}{23}{123}

Covering set-systems are A003465.
Covering set-systems whose dual is strict are A059201.
The T_1 case is A326961.
The BII-numbers of these set-systems are A326966.
The non-covering case is A326968.
The unlabeled version is A326973.
Cf. A006126, A059052, A059523, A326950, A326960, A326965, A326969, A326971, A326974, A326975, A326978.

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}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&stableQ[dual[#],SubsetQ]&]],{n,0,3}]

Inverse binomial transform of A326968.

A326972 Number of unlabeled set-systems on n vertices whose dual is a (strict) antichain, also called unlabeled T_1 set-systems.

Original entry on oeis.org

1, 2, 4, 20, 1232

Offset: 0

Gus Wiseman, Aug 11 2019

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}}. An antichain is a set of sets, none of which is a subset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 20 set-systems:
  {}  {}     {}               {}
      {{1}}  {{1}}            {{1}}
             {{1},{2}}        {{1},{2}}
             {{1},{2},{1,2}}  {{1},{2},{3}}
                              {{1},{2},{1,2}}
                              {{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{2,3}}
                              {{1},{2},{1,3},{2,3}}
                              {{1},{2},{3},{1,2,3}}
                              {{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{1,3},{2,3}}
                              {{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3}}
                              {{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Unlabeled set-systems are A000612.
Unlabeled set-systems whose dual is strict are A326946.
The version with empty edges allowed is A326951.
The labeled version is A326965.
The version where the dual is not required to be strict is A326971.
The covering version is A326974 (first differences).
Cf. A059523, A319559, A319637, A326973, A326976, A326977, A326979.

A326976 Number of factorizations of n into factors > 1 such that every prime factor of n is the GCD of some subset of the factors.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Aug 13 2019

nonn

			The a(72) = 5 factorizations:
  (3*4*6)
  (2*3*12)
  (2*2*3*6)
  (2*3*3*4)
  (2*2*2*3*3)

Factorizations whose dual is a weak antichain are A326975.
T_1 factorizations (whose dual is a strict antichain) are A327012.
T_0 factorizations (whose dual is strict) are A316978.
Cf. A001055, A326947, A326965, A326972, A326974, A326977, A326979.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],n==1||Union[Select[GCD@@@Rest[Subsets[#]],PrimeQ]]==First/@FactorInteger[n]&]],
{n,100}]

A326977 Number of integer partitions of n such that the dual of the multiset partition obtained by factoring each part into prime numbers is a (strict) antichain, also called T_1 integer partitions.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 14, 20, 27, 36, 49, 64, 85, 109, 141, 181, 234, 294, 375, 470, 589, 733, 917, 1131, 1401, 1720, 2113, 2581, 3153, 3833, 4655, 5631, 6801, 8192, 9849, 11816, 14148, 16899, 20153, 23990, 28503, 33815, 40038, 47330, 55858, 65841, 77475

Offset: 0

Gus Wiseman, Aug 13 2019

nonn

The dual of a multiset partition 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}}. An antichain is a set of multisets, none of which is a submultiset of any other.

			The a(0) = 1 through a(7) = 14 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (33)      (7)
           (11)  (21)   (22)    (32)     (42)      (43)
                 (111)  (31)    (41)     (51)      (52)
                        (211)   (221)    (222)     (322)
                        (1111)  (311)    (321)     (331)
                                (2111)   (411)     (421)
                                (11111)  (2211)    (511)
                                         (3111)    (2221)
                                         (21111)   (3211)
                                         (111111)  (4111)
                                                   (22111)
                                                   (31111)
                                                   (211111)
                                                   (1111111)

T_0 integer partitions are A319564.
Set-systems whose dual is a (strict) antichain are A326965.
The version where the dual is a weak antichain is A326978.
T_1 factorizations (whose dual is a strict antichain) are A327012.
Cf. A000041, A319728, A326961, A326974, A326976, A326979.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
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}];
submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@dual[primeMS/@#]&&stableQ[dual[primeMS/@#],submultQ]&]],{n,0,30}]

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

A326968 Number of set-systems on n vertices whose dual is a weak antichain.

Original entry on oeis.org

1, 2, 6, 56, 19446

Offset: 0

Gus Wiseman, Aug 10 2019

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.

			The a(0) = 1 through a(2) = 6 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{2},{1,2}}

The case with strict dual is A326965.
The BII-numbers of these set-systems are A326966.
The version with empty edges allowed is A326969.
The covering case is A326970.
The unlabeled version is A326971.
Cf. A058891, A059523, A326940, A326972, A326973, A326975, A326978, A326979.

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}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

a(n) = A326969(n)/2.

Binomial transform of A326970.

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Original entry on oeis.org

2, 4, 8, 40, 2464

Offset: 0

Gus Wiseman, Aug 13 2019

Alternatively, these are unlabeled sets of subsets of {1..n} whose dual is a (strict) antichain, also called T_1 sets of subsets. 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. An antichain is a set of subsets where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{},{1}}
                  {{1},{2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Unlabeled sets of subsets are A003180.
Unlabeled T_0 sets of subsets are A326949.
The labeled version is A326967.
The case without empty edges is A326972.
The covering case is A327011 (first differences).
Cf. A003181, A059052, A326960, A326965, A326969, A326974, A326976.

a(n) = 2 * A326972(n).

a(n) = Sum_{k = 0..n} A327011(k).

cp's OEIS Frontend

A326961 Number of set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called covering T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326974 Number of unlabeled set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called unlabeled covering T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326979 BII-numbers of T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326970 Number of set-systems covering n vertices whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326972 Number of unlabeled set-systems on n vertices whose dual is a (strict) antichain, also called unlabeled T_1 set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

A326976 Number of factorizations of n into factors > 1 such that every prime factor of n is the GCD of some subset of the factors.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326977 Number of integer partitions of n such that the dual of the multiset partition obtained by factoring each part into prime numbers is a (strict) antichain, also called T_1 integer partitions.

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

A326968 Number of set-systems on n vertices whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica