A326969 -id:A326969 - 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.

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).

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

A326978 Number of integer partitions of n such that the dual of the multiset partition obtained by factoring each part into prime numbers is a weak antichain.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 21, 28, 38, 52, 68, 91, 116, 149, 191, 249, 311, 399, 498, 622, 773, 971, 1193, 1478, 1811, 2222, 2709, 3311, 4021, 4882, 5894, 7110, 8554, 10273, 12312, 14734, 17578, 20941, 24905, 29570, 35056, 41475, 48983, 57752, 68025, 79988

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

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

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

Set-systems whose dual is a weak antichain are A326968.
Factorizations whose dual is a weak antichain are A326975.
The version where the dual is a strict antichain is A326977.
Cf. A000041, A319564, A319728, A326966, A326969, A326970, A326971, A326973.

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],stableQ[dual[primeMS/@#],submultQ]&]],{n,0,30}]

A326967 Number of 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, 10, 92, 38362, 4020654364, 18438434849260080818, 340282363593610212050791236025945013956, 115792089237316195072053288318104625957065868613454666314675263144628100544274

Offset: 0

Gus Wiseman, Aug 10 2019

nonn

Alternatively, these are 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. 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.

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

Sets of subsets are A001146.
The unlabeled version is A326951.
The covering version is A326960.
The case without empty edges is A326965.
Sets of subsets whose dual is a weak antichain are A326969.
Cf. A059052, A059523, A326941, A326966, A326972, A326976, A326977, A326979.

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

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

Binomial transform of A326960.

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

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

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

A326978 Number of integer partitions of n such that the dual of the multiset partition obtained by factoring each part into prime numbers is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula