A072447 -id:A072447 - cp's OEIS frontend

A326866 Number of connectedness systems on n vertices.

1, 2, 8, 96, 6720, 8130432, 1196099819520

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 two overlapping edges.

			The a(0) = 1 through a(2) = 8 connectedness systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

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

The case without singletons is A072446.
The unlabeled case is A326867.
The connected case is A326868.
Binomial transform of A326870 (the covering case).
The BII-numbers of these set-systems are A326872.
Cf. A072444, A072447, A102896, A306445.

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

a(n) = 2^n * A072446(n).

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

A102894 Number of ACI algebras or semilattices on n generators, with no identity or annihilator.

Original entry on oeis.org

1, 1, 4, 45, 2271, 1373701, 75965474236, 14087647703920103947

Offset: 0

Mitch Harris, Jan 18 2005

Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain both the universe and the empty set.
An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
Also the number of set-systems covering n vertices that are closed under union. The BII-numbers of these set-systems are given by A326875. - Gus Wiseman, Aug 01 2019
Number of strict closure operators on a set of n elements, where the closure operator is said to be strict if the empty set is closed. - Tian Vlasic, Jul 30 2022

			From _Gus Wiseman_, Aug 01 2019: (Start)
The a(3) = 45 set-systems with {} and {1,2,3} that are closed under intersection are the following ({} and {1,2,3} not shown). The BII-numbers of these set-systems are given by A326880.
0   {1}   {1}{2}   {1}{2}{3}    {1}{2}{3}{12}   {1}{2}{3}{12}{13}
    {2}   {1}{3}   {1}{2}{12}   {1}{2}{3}{13}   {1}{2}{3}{12}{23}
    {3}   {2}{3}   {1}{2}{13}   {1}{2}{3}{23}   {1}{2}{3}{13}{23}
    {12}  {1}{12}  {1}{2}{23}   {1}{2}{12}{13}
    {13}  {1}{13}  {1}{3}{12}   {1}{2}{12}{23}
    {23}  {1}{23}  {1}{3}{13}   {1}{3}{12}{13}        {1}{2}{3}{12}{13}{23}
          {2}{12}  {1}{3}{23}   {1}{3}{13}{23}
          {2}{13}  {2}{3}{12}   {2}{3}{12}{23}
          {2}{23}  {2}{3}{13}   {2}{3}{13}{23}
          {3}{12}  {2}{3}{23}
          {3}{13}  {1}{12}{13}
          {3}{23}  {2}{12}{23}
                   {3}{13}{23}
(End)

G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967.
Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.
E. H. Moore, Introduction to a Form of General Analysis, AMS Colloquium Publication 2 (1910), pp. 53-80.

Maria Paola Bonacina and Nachum Dershowitz, Canonical ground Horn theories, Lecture Notes in Computer Science 7797, 35-71 (2013).
P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010).
N. Dershowitz, G. S. Huang and M. Harris, Enumeration Problems Related to Ground Horn Theories, arXiv:cs/0610054v2 [cs.LO], 2006-2008.
Christopher S. Flippen, Minimal Sets, Union-Closed Families, and Frankl's Conjecture, Master's thesis, Virginia Commonwealth Univ., 2023.
M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

Regarding set-systems covering n vertices closed under union:
- The non-covering case is A102896.
- The BII-numbers of these set-systems are A326875.
- The case with intersection instead of union is A326881.
- The unlabeled case is A108798.
Cf. A003465, A072447, A102895, A102897, A108800, A193674, A193675, A306445, A326870, A326880, A326883.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Union@@@Tuples[#,2]]&]],{n,0,3}] (* Gus Wiseman, Aug 01 2019 *)

Inverse binomial transform of A102896.

For asymptotics see A102897.

Additional comments from Don Knuth, Jul 01 2005

A326867 Number of unlabeled connectedness systems on n vertices.

Original entry on oeis.org

1, 2, 6, 30, 466, 80926, 1689195482

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.

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

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

The case without singletons is A072444.
The labeled case is A326866.
The connected case is A326869.
Partial sums of A326871 (the covering case).
Cf. A072445, A072446, A072447, A102896, A306445, A326870, A326872.

a(5) from Andrew Howroyd, Aug 10 2019

a(6) from Andrew Howroyd, Oct 28 2023

A072446 Number of connectedness systems on n vertices that contain all singletons.

Original entry on oeis.org

1, 1, 2, 12, 420, 254076, 18689059680

Offset: 0

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

nonn

From Gus Wiseman, Jul 31 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 connectedness systems on n vertices without singleton edges. The BII-numbers of these set-systems are given by A326873. The a(3) = 12 connectedness systems without singletons are:
  {}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{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}}
(End)

			a(3)=12 because of the 12 sets:
{{1}, {2}, {3}};
{{1}, {2}, {3}, {1, 2}};
{{1}, {2}, {3}, {1, 3}};
{{1}, {2}, {3}, {2, 3}};
{{1}, {2}, {3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {2, 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, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

The unlabeled case is A072444.
Exponential transform of A072447 (the connected case).
The case with singletons is A326866.
Binomial transform of A326877 (the covering case).
Cf. A102896, A306445, A326872, A326873.

Table[Length[Select[Subsets[Subsets[Range[n],{2,n}]],SubsetQ[#,Union@@@Select[Tuples[#,2],Intersection@@#!={}&]]&]],{n,0,3}] (* Gus Wiseman, Jul 31 2019 *)

a(n) = A326866(n)/2^n. - Gus Wiseman, Jul 31 2019

a(6) corrected and definition reformulated by Christian Sievers, Oct 26 2023

a(0)=1 prepended by Sean A. Irvine, Oct 02 2024

A326870 Number of connectedness systems covering n vertices.

Original entry on oeis.org

1, 1, 5, 77, 6377, 8097721, 1196051135917

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.

			The a(2) = 5 connectedness systems:
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

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

Inverse binomial transform of A326866 (the non-covering case).
Exponential transform of A326868 (the connected case).
The unlabeled case is A326871.
The BII-numbers of these set-systems are A326872.
The case without singletons is A326877.
Cf. A072445, A072446, A072447, A102896, A323818, A326867, A326869.

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

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

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.

Original entry on oeis.org

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

cp's OEIS Frontend

A326866 Number of connectedness systems on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102894 Number of ACI algebras or semilattices on n generators, with no identity or annihilator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326867 Number of unlabeled connectedness systems on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A072446 Number of connectedness systems on n vertices that contain all singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326870 Number of connectedness systems covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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