A326866 -id:A326866 - cp's OEIS frontend

A072445 Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; {1,2,...,n} is an element of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S. The sets S are counted modulo permutations on the elements 1,2,...,n.

1, 1, 1, 4, 40, 3044, 26894586

Offset: 0

Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002

We define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices. Then a(n) is the number of unlabeled connected connectedness systems without singletons on n vertices. - Gus Wiseman, Aug 01 2019

			a(3) = 4 because of the 4 sets: {{1}, {2}, {3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Wim van Dam, Sub Power Set Sequences
Gus Wiseman, Non-isomorphic representatives of the a(4) = 40 connected connectedness systems without singletons.

The non-connected case is A072444.
The labeled case is A072447.
The case with singletons is A326869.
Cf. A072446, A092918, A108798, A326866, A326867, A326871, A326879.

Inverse Euler transform of A072444. - Andrew Howroyd, Oct 28 2023

a(0)=1 prepended and a(6) corrected by Andrew Howroyd, Oct 28 2023

A072444 Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S. The sets S are counted modulo permutations on the elements 1,2,...,n.

Original entry on oeis.org

1, 1, 2, 6, 47, 3095, 26897732

Offset: 0

Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002

From Gus Wiseman, Aug 01 2019: (Start)
If we define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges, then a(n) is the number of unlabeled connectedness systems on n vertices without singleton edges. Non-isomorphic representatives of the a(3) = 6 connectedness systems without singletons are:
  {}
  {{1,2}}
  {{1,2,3}}
  {{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}
(End)

			a(3) = 6 because of the 6 sets: {{1}, {2}, {3}}; {{1}, {2}, {3}, {1, 2}}; {{1}, {2}, {3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Wim van Dam, Sub Power Set Sequences

The connected case is A072445.
The labeled case is A072446.
Unlabeled set-systems closed under union are A193674.
Unlabeled connectedness systems are A326867.
Cf. A072447, A092918, A326866, A326871, A326873.

Euler transform of A072445. - Andrew Howroyd, Oct 28 2023

a(0)=1 prepended and a(6) corrected by Andrew Howroyd, Oct 28 2023

A326869 Number of unlabeled connected connectedness systems on n vertices.

Original entry on oeis.org

1, 1, 3, 20, 406, 79964, 1689032658

Offset: 0

Gus Wiseman, Jul 29 2019

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it contains an edge with all the vertices.

			Non-isomorphic representatives of the a(3) = 20 connected connectedness systems:
  {{1,2,3}}
  {{3},{1,2,3}}
  {{2,3},{1,2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1},{3},{2,3},{1,2,3}}
  {{2},{3},{2,3},{1,2,3}}
  {{2},{1,3},{2,3},{1,2,3}}
  {{3},{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{2,3},{1,2,3}}
  {{1},{2},{1,3},{2,3},{1,2,3}}
  {{2},{3},{1,3},{2,3},{1,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}}

The case without singletons is A072445.
Connected set-systems are A092918.
The not necessarily connected case is A326867.
The labeled case is A326868.
Euler transform is A326871 (the covering case).
Cf. A072444, A072446, A072447, A102896, A323818, A326866, A326870, A326879.

a(5) from Andrew Howroyd, Aug 16 2019

a(6) from Andrew Howroyd, Oct 28 2023

A326868 Number of connected connectedness systems on n vertices.

Original entry on oeis.org

1, 1, 4, 64, 6048, 8064000, 1196002238976

Offset: 0

Gus Wiseman, Jul 29 2019

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices.

			The a(3) = 64 connected connectedness systems:
  {{123}}              {{1}{123}}
  {{12}{123}}          {{2}{123}}
  {{13}{123}}          {{3}{123}}
  {{23}{123}}          {{1}{12}{123}}
  {{12}{13}{123}}      {{1}{13}{123}}
  {{12}{23}{123}}      {{1}{23}{123}}
  {{13}{23}{123}}      {{2}{12}{123}}
  {{12}{13}{23}{123}}  {{2}{13}{123}}
                       {{2}{23}{123}}
                       {{3}{12}{123}}
                       {{3}{13}{123}}
                       {{3}{23}{123}}
                       {{1}{12}{13}{123}}
                       {{1}{12}{23}{123}}
                       {{1}{13}{23}{123}}
                       {{2}{12}{13}{123}}
                       {{2}{12}{23}{123}}
                       {{2}{13}{23}{123}}
                       {{3}{12}{13}{123}}
                       {{3}{12}{23}{123}}
                       {{3}{13}{23}{123}}
                       {{1}{12}{13}{23}{123}}
                       {{2}{12}{13}{23}{123}}
                       {{3}{12}{13}{23}{123}}
.
  {{1}{2}{123}}              {{1}{2}{3}{123}}
  {{1}{3}{123}}              {{1}{2}{3}{12}{123}}
  {{2}{3}{123}}              {{1}{2}{3}{13}{123}}
  {{1}{2}{12}{123}}          {{1}{2}{3}{23}{123}}
  {{1}{2}{13}{123}}          {{1}{2}{3}{12}{13}{123}}
  {{1}{2}{23}{123}}          {{1}{2}{3}{12}{23}{123}}
  {{1}{3}{12}{123}}          {{1}{2}{3}{13}{23}{123}}
  {{1}{3}{13}{123}}          {{1}{2}{3}{12}{13}{23}{123}}
  {{1}{3}{23}{123}}
  {{2}{3}{12}{123}}
  {{2}{3}{13}{123}}
  {{2}{3}{23}{123}}
  {{1}{2}{12}{13}{123}}
  {{1}{2}{12}{23}{123}}
  {{1}{2}{13}{23}{123}}
  {{1}{3}{12}{13}{123}}
  {{1}{3}{12}{23}{123}}
  {{1}{3}{13}{23}{123}}
  {{2}{3}{12}{13}{123}}
  {{2}{3}{12}{23}{123}}
  {{2}{3}{13}{23}{123}}
  {{1}{2}{12}{13}{23}{123}}
  {{1}{3}{12}{13}{23}{123}}
  {{2}{3}{12}{13}{23}{123}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

The case without singletons is A072447.
The not necessarily connected case is A326866.
The unlabeled case is A326869.
The BII-numbers of these set-systems are A326879.
Cf. A072445, A072446, A102896, A306445, A323818, A326867, A326870, A326872.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],n==0||MemberQ[#,Range[n]]&&SubsetQ[#,Union@@@Select[Tuples[#,2],Intersection@@#!={}&]]&]],{n,0,4}]

a(n > 1) = 2^n * A072447(n).

Logarithmic transform of A326870.

a(6) corrected by Christian Sievers, Oct 28 2023

A326871 Number of unlabeled connectedness systems covering n vertices.

Original entry on oeis.org

1, 1, 4, 24, 436, 80460, 1689114556

Offset: 0

Gus Wiseman, Jul 29 2019

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is covering if every vertex belongs to some edge.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 24 connectedness systems:
  {}  {{1}}  {{1,2}}          {{1,2,3}}
             {{1},{2}}        {{1},{2,3}}
             {{2},{1,2}}      {{1},{2},{3}}
             {{1},{2},{1,2}}  {{3},{1,2,3}}
                              {{1},{3},{2,3}}
                              {{2,3},{1,2,3}}
                              {{2},{3},{1,2,3}}
                              {{1},{2,3},{1,2,3}}
                              {{1},{2},{3},{2,3}}
                              {{3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2,3}}
                              {{1,3},{2,3},{1,2,3}}
                              {{1},{3},{2,3},{1,2,3}}
                              {{2},{3},{2,3},{1,2,3}}
                              {{2},{1,3},{2,3},{1,2,3}}
                              {{3},{1,3},{2,3},{1,2,3}}
                              {{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{2,3},{1,2,3}}
                              {{1},{2},{1,3},{2,3},{1,2,3}}
                              {{2},{3},{1,3},{2,3},{1,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}}

The non-covering case without singletons is A072444.
The case without singletons is A326899.
First differences of A326867 (the non-covering case).
Euler transform of A326869 (the connected case).
The labeled case is A326870.
Cf. A072445, A072446, A072447, A193674, A323818, A326866, A326868.

a(5) from Andrew Howroyd, Aug 10 2019

a(6) from Andrew Howroyd, Oct 28 2023

A326901 Number of set-systems (without {}) on n vertices that are closed under intersection.

Original entry on oeis.org

1, 2, 6, 32, 418, 23702, 16554476, 1063574497050, 225402367516942398102

Offset: 0

Gus Wiseman, Aug 04 2019

A set-system is a finite set of finite nonempty sets, so no two edges of a set-system that is closed under intersection can be disjoint.

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

M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

The case with union instead of intersection is A102896.
The case closed under union and intersection is A326900.
The covering case is A326902.
The connected case is A326903.
The unlabeled version is A326904.
The BII-numbers of these set-systems are A326905.
Cf. A000798, A001930, A006058, A102895, A102898, A182507, A326866, A326876, A326878, A326882.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

a(n) = 1 + Sum_{k=0, n-1} binomial(n,k)*A102895(k). - Andrew Howroyd, Aug 10 2019

a(5)-a(8) from Andrew Howroyd, Aug 10 2019

A326964 Number of connected set-systems covering a subset of {1..n}.

Original entry on oeis.org

1, 2, 7, 112, 32253, 2147316942, 9223372023968335715, 170141183460469231667123699322514272668, 5789604461865809771178549250434395393752402807429031284280914691514037561273

Offset: 0

Gus Wiseman, Aug 10 2019

nonn

A set-system is a finite set of finite nonempty sets.

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

Covering sets of subsets are A000371.
Connected graphs are A001187.
The unlabeled version is A309667.
The BII-numbers of connected set-systems are A326749.
The covering case is A323818.
Cf. A007718, A048143, A058891, A092918, A300913, A304716, A326866, A326948.

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]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Length[csm[#]]<=1&]],{n,0,4}]

Binomial transform of A323818.

A326877 Number of connectedness systems covering n vertices without singletons.

Original entry on oeis.org

1, 0, 1, 8, 381, 252080, 18687541309

Offset: 0

Gus Wiseman, Jul 30 2019

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is covering if every vertex belongs to some edge.

			The a(3) = 8 covering connectedness systems without singletons:
  {{1,2,3}}
  {{1,2},{1,2,3}}
  {{1,3},{1,2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{1,2,3}}
  {{1,2},{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Inverse binomial transform of A072446 (the non-covering case).
Exponential transform of A072447 if we assume A072447(1) = 0 (the connected case).
The case with singletons is A326870.
The BII-numbers of these set-systems are A326873.
Cf. A072444, A072445, A102896, A323818, A326866, A326867, A326868, A326871, A326872.

Table[Length[Select[Subsets[Subsets[Range[n],{2,n}]],Union@@#==Range[n]&&SubsetQ[#,Union@@@Select[Tuples[#,2],Intersection@@#!={}&]]&]],{n,0,4}]

a(6) corrected by Christian Sievers, Oct 28 2023

A326879 BII-numbers of connected connectedness systems.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 7, 8, 16, 17, 24, 25, 32, 34, 40, 42, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112

Offset: 1

Gus Wiseman, Jul 29 2019

nonn

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it contains an edge containing all the vertices.
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 enumeration of connected connectedness systems by number of vertices is given by A326868.

			The sequence of all connected connectedness systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  67: {{1},{2},{1,2,3}}
  68: {{1,2},{1,2,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Connected connectedness systems are counted by A326868, with unlabeled version A326869.
Connected connectedness systems without singletons are counted by A072447.
The not necessarily connected case is A326872.
Cf. A029931, A048793, A072445, A072446, A326031, A326749, A326753, A326866, A326867, A326870, A326876.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
connsysQ[eds_]:=SubsetQ[eds,Union@@@Select[Tuples[eds,2],Intersection@@#!={}&]];
Select[Range[0,100],#==0||MemberQ[bpe/@bpe[#],Union@@bpe/@bpe[#]]&&connsysQ[bpe/@bpe[#]]&]

A326873 BII-numbers of connectedness systems without singletons.

Original entry on oeis.org

0, 4, 16, 32, 64, 68, 80, 84, 96, 100, 112, 116, 256, 288, 512, 528, 1024, 1028, 1280, 1284, 1536, 1540, 1792, 1796, 2048, 2052, 4096, 4112, 4352, 4368, 6144, 6160, 6400, 6416, 8192, 8224, 8704, 8736, 10240, 10272, 10752, 10784, 16384, 16388, 16400, 16416

Offset: 1

Gus Wiseman, Jul 29 2019

nonn

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges.
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 enumeration of these set-systems by number of covered vertices is given by A326877.

			The sequence of all connectedness systems without singletons together with their BII-numbers begins:
     0: {}
     4: {{1,2}}
    16: {{1,3}}
    32: {{2,3}}
    64: {{1,2,3}}
    68: {{1,2},{1,2,3}}
    80: {{1,3},{1,2,3}}
    84: {{1,2},{1,3},{1,2,3}}
    96: {{2,3},{1,2,3}}
   100: {{1,2},{2,3},{1,2,3}}
   112: {{1,3},{2,3},{1,2,3}}
   116: {{1,2},{1,3},{2,3},{1,2,3}}
   256: {{1,4}}
   288: {{2,3},{1,4}}
   512: {{2,4}}
   528: {{1,3},{2,4}}
  1024: {{1,2,4}}
  1028: {{1,2},{1,2,4}}
  1280: {{1,4},{1,2,4}}
  1284: {{1,2},{1,4},{1,2,4}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Connectedness systems without singletons are counted by A072446, with unlabeled case A072444.
Connectedness systems are counted by A326866, with unlabeled case A326867.
BII-numbers of connectedness systems are A326872.
The connected case is A326879.
Cf. A029931, A048793, A072447, A326031, A326749, A326750, A326870, A326875, A326877.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
connnosQ[eds_]:=!MemberQ[Length/@eds,1]&&SubsetQ[eds,Union@@@Select[Tuples[eds,2],Intersection@@#!={}&]];
Select[Range[0,1000],connnosQ[bpe/@bpe[#]]&]

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A072444 Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S. The sets S are counted modulo permutations on the elements 1,2,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A326869 Number of unlabeled connected connectedness systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A326868 Number of connected connectedness systems on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326871 Number of unlabeled connectedness systems covering n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A326901 Number of set-systems (without {}) on n vertices that are closed under intersection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326964 Number of connected set-systems covering a subset of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326877 Number of connectedness systems covering n vertices without singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica