A326978 -id:A326978 - cp's OEIS frontend

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

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.

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

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

Original entry on oeis.org

1, 1, 3, 19, 1243

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}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 19 set-systems:
  {}  {{1}}  {{1,2}}          {{1,2,3}}
             {{1},{2}}        {{1},{2,3}}
             {{1},{2},{1,2}}  {{1},{2},{3}}
                              {{1,2},{1,3},{2,3}}
                              {{1},{2,3},{1,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 covering set-systems are A055621.
The labeled version is A326970.
The non-covering case is A326971 (partial sums).
The case that is also T_0 is the T_1 case A326974.
Cf. A000612, A059523, A319637, A326966, A326968, A326972, A326975, A326978.

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.

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

Original entry on oeis.org

1, 2, 5, 24, 1267

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.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 24 set-systems:
  {}  {}     {}               {}
      {{1}}  {{1}}            {{1}}
             {{1,2}}          {{1,2}}
             {{1},{2}}        {{1},{2}}
             {{1},{2},{1,2}}  {{1,2,3}}
                              {{1},{2,3}}
                              {{1},{2},{3}}
                              {{1},{2},{1,2}}
                              {{1,2},{1,3},{2,3}}
                              {{1},{2,3},{1,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 labeled version is A326968.
The version with empty edges allowed is A326969.
The T_0 case (with strict dual) is A326972.
The covering case is A326973 (first differences).
Cf. A319559, A326951, A326965, A326966, A326970, A326974, A326975, A326978.

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

A326969 Number of sets of subsets of {1..n} whose dual is a weak antichain.

Original entry on oeis.org

2, 4, 12, 112, 38892

Offset: 0

Gus Wiseman, Aug 10 2019

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}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

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

Sets of subsets whose dual is strict are A326941.
The BII-numbers of set-systems whose dual is a weak antichain are A326966.
Sets of subsets whose dual is a (strict) antichain are A326967.
The case without empty edges is A326968.
Cf. A001146, A059052, A326951, A326970, A326971, 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]]],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

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

a(n) = 2 * Sum_{k = 0..n} binomial(n, k) * A326970(k).

A327018 Number of non-isomorphic set-systems of weight n whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 17, 24, 51, 80, 180

Offset: 0

Gus Wiseman, Aug 15 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.

			Non-isomorphic representatives of the a(1) = 1 through a(6) = 17 multiset partitions:
  {1}  {12}    {123}      {1234}        {12345}          {123456}
       {1}{2}  {1}{23}    {1}{234}      {1}{2345}        {1}{23456}
               {1}{2}{3}  {12}{34}      {12}{345}        {12}{3456}
                          {1}{2}{12}    {1}{2}{345}      {123}{456}
                          {1}{2}{34}    {1}{23}{45}      {12}{13}{23}
                          {1}{2}{3}{4}  {1}{2}{3}{23}    {1}{23}{123}
                                        {1}{2}{3}{45}    {1}{2}{3456}
                                        {1}{2}{3}{4}{5}  {1}{23}{456}
                                                         {12}{34}{56}
                                                         {1}{2}{13}{23}
                                                         {1}{2}{3}{123}
                                                         {1}{2}{3}{456}
                                                         {1}{2}{34}{56}
                                                         {3}{4}{12}{34}
                                                         {1}{2}{3}{4}{34}
                                                         {1}{2}{3}{4}{56}
                                                         {1}{2}{3}{4}{5}{6}

Cf. A007716, A283877, A293993, A319643, A319721, A326966, A326968, A326970, A326972, A326973, A326974, A326975, A326978, A327017, A327019.

A319643 Number of non-isomorphic weight-n strict multiset partitions whose dual is an antichain of (not necessarily distinct) multisets.

Original entry on oeis.org

1, 1, 3, 6, 15, 29, 82, 179, 504, 1302, 3822

Offset: 0

Gus Wiseman, Sep 25 2018

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
From Gus Wiseman, Aug 15 2019: (Start)
Also the number of non-isomorphic T_0 weak antichains of weight n. The T_0 condition means that the dual is strict (no repeated edges). A weak antichain is a multiset of multisets, none of which is a proper submultiset of any other. For example, non-isomorphic representatives of the a(0) = 1 through a(4) = 15 T_0 weak antichains are:
  {}  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}
             {{1},{1}}  {{1,2,2}}      {{1,2,2,2}}
             {{1},{2}}  {{1},{2,2}}    {{1,1},{1,1}}
                        {{1},{1},{1}}  {{1,1},{2,2}}
                        {{1},{2},{2}}  {{1},{2,2,2}}
                        {{1},{2},{3}}  {{1,2},{2,2}}
                                       {{1},{2,3,3}}
                                       {{1,3},{2,3}}
                                       {{1},{1},{2,2}}
                                       {{1},{2},{3,3}}
                                       {{1},{1},{1},{1}}
                                       {{1},{1},{2},{2}}
                                       {{1},{2},{2},{2}}
                                       {{1},{2},{3},{3}}
                                       {{1},{2},{3},{4}}
(End)

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

Cf. A006126, A007716, A059201, A283877, A293606, A316980, A316983, A318099, A319558, A319616-A319646.

Cf. A245567, A293993, A319721, A326704, A326950, A326973, A326978.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326969 Number of sets of subsets of {1..n} whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327018 Number of non-isomorphic set-systems of weight n whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

A319643 Number of non-isomorphic weight-n strict multiset partitions whose dual is an antichain of (not necessarily distinct) multisets.