A327040 -id:A327040 - cp's OEIS frontend

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

0, 1, 0, 24, 1984

Offset: 0

Gus Wiseman, Sep 01 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain in a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity.

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

The BII-numbers of these set-systems are A327098.
The same for cut-connectivity 2 is A327113.
The non-covering version is A327128.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327114, A327126, A327229.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]

Inverse binomial transform of A327128.

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 3, 62, 24710, 2076948136, 9221293198653529144, 170141182628636920684331812494864430896

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}}. This sequence counts covering set-systems whose dual is strict and pairwise intersecting.

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

The pairwise intersecting case is A319774.
The BII-numbers of these set-systems are the intersection of A326947 and A326853.
The non-T_0 version is A327040.
The non-covering version is A327052.
Cf. A003465, A305843, A319767, A326854, A327020, A327037, A327039.

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

Inverse binomial transform of A327052.

a(5)-a(7) from Christian Sievers, Feb 04 2024

A327100 BII-numbers of antichains of sets with cut-connectivity 1.

Original entry on oeis.org

1, 2, 8, 20, 36, 48, 128, 260, 272, 276, 292, 304, 308, 320, 516, 532, 544, 548, 560, 564, 576, 768, 784, 788, 800, 804, 1040, 1056, 2064, 2068, 2080, 2084, 2096, 2100, 2112, 2304, 2308, 2324, 2336, 2352, 2560, 2564, 2576, 2596, 2608, 2816, 2820, 2832, 2848

Offset: 1

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

We define the cut-connectivity of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039, A327040), this is the same as vertex-connectivity (A327334, A327051).

			The sequence of all antichains of sets with vertex-connectivity 1 together with their BII-numbers begins:
    1: {{1}}
    2: {{2}}
    8: {{3}}
   20: {{1,2},{1,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
  128: {{4}}
  260: {{1,2},{1,4}}
  272: {{1,3},{1,4}}
  276: {{1,2},{1,3},{1,4}}
  292: {{1,2},{2,3},{1,4}}
  304: {{1,3},{2,3},{1,4}}
  308: {{1,2},{1,3},{2,3},{1,4}}
  320: {{1,2,3},{1,4}}
  516: {{1,2},{2,4}}
  532: {{1,2},{1,3},{2,4}}
  544: {{2,3},{2,4}}
  548: {{1,2},{2,3},{2,4}}
  560: {{1,3},{2,3},{2,4}}
  564: {{1,2},{1,3},{2,3},{2,4}}

Positions of 1's in A326786.
The graphical case is A327114.
BII numbers of antichains with vertex-connectivity >= 1 are A326750.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
Cf. A000120, A000372, A006126, A048143, A048793, A070939, A322390, A326031, A326749, A326751, A327071, A327111.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],stableQ[bpe/@bpe[#],SubsetQ]&&cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]==1&]

If (+) is union and (-) is complement, we have A327100 = A058891 + (A326750 - A326751).

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Original entry on oeis.org

0, 1, 2, 27, 2084

Offset: 0

Gus Wiseman, Sep 02 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. We define the cut-connectivity (A326786, A327237, A327126) of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039, A327040), this is the same as vertex-connectivity (A327334, A327051).

The covering version is A327197.
The BII-numbers of these set-systems are A327098.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327113, A327114, A327126, A327229.

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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],cutConnSys[Union@@#,#]==1&]],{n,0,3}]

Binomial transform of A327197.

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Original entry on oeis.org

0, 2, 4, 8, 16, 32, 34, 40, 64, 128, 130, 160, 256, 260, 288, 512, 514, 520, 544, 640, 1024, 2048, 2050, 2052, 2056, 2082, 2088, 2176, 2178, 2208, 2304, 2560, 2568, 2592, 4096, 8192, 8194, 8200, 8224, 8226, 8232, 8320, 8704, 8706, 8832, 10240, 10248, 10368

Offset: 1

Gus Wiseman, Oct 06 2020

nonn

Differs from A291165 in having 1090535424, corresponding to the composition (6,10,15).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
       0: ()        512: (10)       2304: (3,9)
       2: (2)       514: (8,2)      2560: (2,10)
       4: (3)       520: (6,4)      2568: (2,6,4)
       8: (4)       544: (4,6)      2592: (2,4,6)
      16: (5)       640: (2,8)      4096: (13)
      32: (6)      1024: (11)       8192: (14)
      34: (4,2)    2048: (12)       8194: (12,2)
      40: (2,4)    2050: (10,2)     8200: (10,4)
      64: (7)      2052: (9,3)      8224: (8,6)
     128: (8)      2056: (8,4)      8226: (8,4,2)
     130: (6,2)    2082: (6,4,2)    8232: (8,2,4)
     160: (2,6)    2088: (6,2,4)    8320: (6,8)
     256: (9)      2176: (4,8)      8704: (4,10)
     260: (6,3)    2178: (4,6,2)    8706: (4,8,2)
     288: (3,6)    2208: (4,2,6)    8832: (4,2,8)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

A318719 gives the Heinz numbers of the unordered version, with non-strict version A337694.
A337667 counts the non-strict version.
A337983 counts these compositions, with unordered version A318717.
A051185 counts intersecting set-systems, with spanning case A305843.
A200976 and A328673 count the unordered non-strict version.
A337462 counts pairwise coprime compositions.
A318749 counts pairwise non-coprime factorizations, with strict case A319786.
All of the following pertain to compositions in standard order (A066099):
- A000120 is length.
- A070939 is sum.
- A124767 counts runs.
- A233564 ranks strict compositions.
- A272919 ranks constant compositions.
- A333219 is Heinz number.
- A333227 ranks pairwise coprime compositions, or A335235 if singletons are considered coprime.
- A333228 ranks compositions whose distinct parts are pairwise coprime.
- A335236 ranks compositions neither a singleton nor pairwise coprime.
- A337561 is the pairwise coprime instead of pairwise non-coprime version, or A337562 if singletons are considered coprime.
- A337666 ranks the non-strict version.
Cf. A082024, A101268, A302797, A305713, A319752, A327040, A327516, A336737, A337599, A337604, A337605.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Select[Range[0,1000],UnsameQ@@stc[#]&&stabQ[stc[#],CoprimeQ]&]

Intersection of A337666 and A233564.

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 16, 17, 24, 32, 34, 40, 52, 64, 65, 66, 68, 69, 70, 72, 80, 81, 84, 85, 88, 96, 98, 100, 102, 104, 112, 116, 120, 128, 256, 257, 384, 512, 514, 640, 772, 1024, 1025, 1026, 1028, 1029, 1030, 1152, 1280, 1281, 1284, 1285, 1408, 1536, 1538

Offset: 1

Gus Wiseman, Aug 18 2019

nonn

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}}. This sequence gives all BII-numbers (defined below) of pairwise intersecting set-systems whose dual is also pairwise intersecting.

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

			The sequence of all pairwise intersecting, cointersecting set-systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}

The unlabeled multiset partition version is A319765.
Equals the intersection of A326853 and A326910.
The T_0 version is A326854.
These set-systems are counted by A327037 (covering) and A327038 (not covering).
Cf. A029931, A048793, A051185, A305843, A319774, A326031, A327039, A327040, A327041, A327057.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
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,100],stableQ[bpe/@bpe[#],Intersection[#1,#2]=={}&]&&stableQ[dual[bpe/@bpe[#]],Intersection[#1,#2]=={}&]&]

cp's OEIS Frontend

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327100 BII-numbers of antichains of sets with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica