A102896 -id:A102896 - cp's OEIS frontend

A326877 Number of connectedness systems covering n vertices without singletons.

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

A334254 Number of closure operators on a set of n elements which satisfy the T_1 separation axiom.

Original entry on oeis.org

1, 2, 1, 8, 545, 702525, 66960965307

Offset: 0

Joshua Moerman, Apr 20 2020

The T_1 axiom states that all singleton sets {x} are closed.

For n>1, this property implies strictness (meaning that the empty set is closed).

			The a(3) = 8 set-systems of closed sets:
  {{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},{}}

Dmitry I. Ignatov, On the Cryptomorphism between Davis' Subset Lattices, Atomic Lattices, and Closure Systems under T1 Separation Axiom, arXiv:2209.12256 [cs.DM], 2022.
Dmitry I. Ignatov, Supporting iPython code for counting closure systems w.r.t. the T_1 separation axiom, Github repository
Dmitry I. Ignatov, PDF of the supporting iPython notebook
S. Mapes, Finite atomic lattices and resolutions of monomial ideals, J. Algebra, 379 (2013), 259-276.
Eric Weisstein's World of Mathematics, Separation Axioms
Wikipedia, Separation Axiom

The number of all closure operators is given in A102896.
For T_0 closure operators, see A334252.
For strict T_1 closure operators, see A334255, the only difference is a(1).
Cf. A326960, A326961, A326979.

a(6) from Dmitry I. Ignatov, Jul 03 2022

A326900 Number of set-systems on n vertices that are closed under union and intersection.

Original entry on oeis.org

1, 2, 6, 29, 232, 3032, 62837, 2009408, 97034882, 6952703663, 728107141058, 109978369078580, 23682049666957359, 7195441649260733390, 3056891748255795885338, 1801430622263459795017565, 1462231768717868324127642932, 1624751185398704445629757084188, 2457871026957756859612862822442301

Offset: 0

Gus Wiseman, Aug 04 2019

nonn

A set-system is a finite set of finite nonempty sets, so no two edges of such a set-system can be disjoint.

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

Binomial transform of A006058 (the covering case).
The case closed under union only is A102896.
The case with {} allowed is A306445.
The BII-numbers of these set-systems are A326876.
The case closed under intersection only is A326901.
The unlabeled version is A326908.
Cf. A000798, A001930, A102895, A102898, A326866, A326878, A326882.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],SubsetQ[#,Union[Union@@@Tuples[#,2],Intersection@@@Tuples[#,2]]]&]],{n,0,3}]
(* Second program: *)
A006058 = Cases[Import["https://oeis.org/A006058/b006058.txt", "Table"], {, }][[All, 2]];
a[n_] := Sum[Binomial[n, k] A006058[[k + 1]], {k, 0, n}];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 01 2020 *)

a(16)-a(18) from A006058 by Jean-François Alcover, Jan 01 2020

A326903 Number of set-systems (without {}) on n vertices that are closed under intersection and have an edge containing all of the vertices, or Moore families without {}.

Original entry on oeis.org

0, 1, 3, 16, 209, 11851, 8277238, 531787248525, 112701183758471199051

Offset: 0

Gus Wiseman, Aug 04 2019

A set-system is a finite set of finite nonempty sets, so no two edges of such a set-system can be disjoint.

If {} is allowed, we get Moore families (A102896, cf A102895).

			The a(1) = 1 through a(3) = 16 set-systems:
  {{1}}  {{1,2}}      {{1,2,3}}
         {{1},{1,2}}  {{1},{1,2,3}}
         {{2},{1,2}}  {{2},{1,2,3}}
                      {{3},{1,2,3}}
                      {{1,2},{1,2,3}}
                      {{1,3},{1,2,3}}
                      {{2,3},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1},{1,3},{1,2,3}}
                      {{2},{1,2},{1,2,3}}
                      {{2},{2,3},{1,2,3}}
                      {{3},{1,3},{1,2,3}}
                      {{3},{2,3},{1,2,3}}
                      {{1},{1,2},{1,3},{1,2,3}}
                      {{2},{1,2},{2,3},{1,2,3}}
                      {{3},{1,3},{2,3},{1,2,3}}

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

The case closed under union and intersection is A006058.
The case with union instead of intersection is A102894.
The unlabeled version is A193674.
The case without requiring the maximum edge is A326901.
The covering case is A326902.
Cf. A000798, A001930, A102895, A102898, A326866, A326876, A326878, A326882, A326904.

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

a(n) = A326901(n) / 2 for n > 0. - Andrew Howroyd, Aug 10 2019

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

A102499 Primes of the concatenated form 3nn3.

Original entry on oeis.org

313133, 323233, 328283, 329293, 338383, 343433, 349493, 350503, 352523, 356563, 364643, 367673, 380803, 383833, 392923, 394943, 395953, 397973, 3100010003, 3100310033, 3102410243, 3102510253, 3102810283, 3103910393, 3104610463

Offset: 1

Mark Hudson (mrmarkhudson(AT)hotmail.com), Jan 13 2005

			313133 is prime and of the form 3nn3 for n=13.
3100010003 is prime and of the form 3nn3 for n=1000.

Cf. A102896 for sequence of all numbers of form 3nn3. A102498 for the n values corresponding to the primes in this sequence.

mn[n_]:=Module[{idn=IntegerDigits[n]}, FromDigits[Join[{3},idn,idn,{3}]]]; Select[ mn/@ Range[ 1100],PrimeQ]  (* Harvey P. Dale, Feb 04 2011 *)

A326874 BII-numbers of abstract simplicial complexes.

Original entry on oeis.org

0, 1, 2, 3, 7, 8, 9, 10, 11, 15, 25, 27, 31, 42, 43, 47, 59, 63, 127, 128, 129, 130, 131, 135, 136, 137, 138, 139, 143, 153, 155, 159, 170, 171, 175, 187, 191, 255, 385, 387, 391, 393, 395, 399, 409, 411, 415, 427, 431, 443, 447, 511, 642, 643, 647, 650, 651, 655

Offset: 1

Gus Wiseman, Jul 29 2019

nonn

An abstract simplicial complex is a set of finite nonempty sets (edges) that is closed under taking a nonempty subset of any edge.
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 abstract simplicial complexes by number of covered vertices is given by A307249.

			The sequence of all abstract simplicial complexes together with their BII-numbers begins:
    0: {}
    1: {{1}}
    2: {{2}}
    3: {{1},{2}}
    7: {{1},{2},{1,2}}
    8: {{3}}
    9: {{1},{3}}
   10: {{2},{3}}
   11: {{1},{2},{3}}
   15: {{1},{2},{1,2},{3}}
   25: {{1},{3},{1,3}}
   27: {{1},{2},{3},{1,3}}
   31: {{1},{2},{3},{1,2},{1,3}}
   42: {{2},{3},{2,3}}
   43: {{1},{2},{3},{2,3}}
   47: {{1},{2},{3},{1,2},{2,3}}
   59: {{1},{2},{3},{1,3},{2,3}}
   63: {{1},{2},{3},{1,2},{1,3},{2,3}}
  127: {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
  128: {{4}}
  129: {{1},{4}}

Wikipedia, Abstract simplicial complex

Cf. A006126, A014466, A029931, A048793, A102896, A261005, A307249, A326031, A326872, A326876.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],SubsetQ[bpe/@bpe[#],DeleteCases[Union@@Subsets/@bpe/@bpe[#],{}]]&]

A326913 BII-numbers of set-systems (without {}) closed under union and intersection.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 16, 17, 24, 32, 34, 40, 64, 65, 66, 68, 69, 70, 72, 80, 81, 85, 88, 96, 98, 102, 104, 120, 128, 256, 257, 384, 512, 514, 640, 1024, 1025, 1026, 1028, 1029, 1030, 1152, 1280, 1281, 1285, 1408, 1536, 1538, 1542, 1664, 1920, 2048, 2056, 2176

Offset: 1

Gus Wiseman, Aug 04 2019

nonn

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.

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 closed under union and intersection 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}}
  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}}
  72: {{3},{1,2,3}}

Cf. A048793, A102894, A102895, A102896, A102897, A326031, A326875, A326876, A326878, A326880, A326901.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],SubsetQ[bpe/@bpe[#],Union@@@Tuples[bpe/@bpe[#],2]]&&SubsetQ[bpe/@bpe[#],Intersection@@@Tuples[bpe/@bpe[#],2]]&]

A334252 Number of closure operators on a set of n elements which satisfy the T_0 separation axiom.

Original entry on oeis.org

1, 2, 5, 44, 2179, 1362585, 75953166947, 14087646640499308474

Offset: 0

Joshua Moerman, Apr 20 2020

The T_0 axiom states that the closure of {x} and {y} are different for distinct x and y.

			The a(0) = 1 through a(2) = 5 set-systems of closed sets:
{{}}  {{}}      {{1,2},{1}}
      {{1},{}}  {{1,2},{2}}
                {{1,2},{1},{}}
                {{1,2},{2},{}}
                {{1,2},{1},{2},{}}

R. S. R. Myers, J. Adámek, S. Milius, and H. Urbat, Coalgebraic constructions of canonical nondeterministic automata, Theoretical Computer Science, 604 (2015), 81-101.
B. Venkateswarlu and U. M. Swamy, T_0-Closure Operators and Pre-Orders, Lobachevskii Journal of Mathematics, 39 (2018), 1446-1452.

The number of all closure operators is given in A102896.
For strict T0 closure operators, see A334253.
For T1 closure operators, see A334254.
Cf. A326943, A326944, A326945.

a(n) = Sum_{k=0..n} Stirling1(n,k) * A102896(k). - Andrew Howroyd, Apr 20 2020

a(6)-a(7) from Andrew Howroyd, Apr 20 2020

A355315 Triangular array read by rows: T(n,k) is the number of independent collections of subsets of [n] having exactly k members, n>=0, 0<=k<=A347025(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 7, 21, 26, 6, 1, 15, 105, 400, 803, 782, 340, 34

Offset: 0

Geoffrey Critzer, Jun 28 2022

Here, an independent collection of subsets of [n] is such that no member is a union of other members. The empty set is not contained in any independent set although the empty collection is independent. These collections are the bases of the union closed families counted in A102896 which gives the row sums of this sequence.

			T(3,4) = 6 because we have: {{1}, {2}, {1, 3}, {2, 3}}, {{1}, {3}, {1, 2}, {2, 3}}, {{1}, {1, 2}, {1, 3}, {2, 3}}, {{2}, {3}, {1, 2}, {1, 3}}, {{2}, {1, 2}, {1, 3}, {2, 3}}, {{3}, {1, 2}, {1, 3}, {2, 3}}.
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  3,   3;
  1,  7,  21,  26,   6;
  1, 15, 105, 400, 803, 782, 340, 34;
  ...

K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982, page 44.

P. Erdős and D. Kleitman, Extremal problems among subsets of a set, Discrete Mathematics, 8, 1974, 281-294.
D. Kleitman, On a combinatorial problem of Erdős, Proc. Amer. Math Soc, 17 (1966) 139-141.

Columns k=0..2 give: A000012, A000225, A134057.

Row sums give A102896.

independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !
    DuplicateFreeQ[collection], False, Apply[And,Table[! MemberQ[   Map[Clip[Total[#]] &,Subsets[Drop[collection, {i}], {2, Length[collection]}]],
      collection[[i]]], {i, 1, Length[collection]}]]]; Map[Select[#, # > 0 &] &,
  Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, 7}], {nn, 0, 4}]] // Grid

T(n,0) = 1 = A000012(n).
T(n,1) = 2^n - 1 = A000225(n).
T(n,2) = binomial(2^n-1,2) = A134057(n).

A355517 Number of nonisomorphic systems enumerated by A334254; that is, the number of inequivalent closure operators on a set of n elements where all singletons are closed.

Original entry on oeis.org

1, 2, 1, 4, 50, 7443, 95239971

Offset: 0

Dmitry I. Ignatov, Jul 05 2022

The T_1 axiom states that all singleton sets {x} are closed.

For n>1, this property implies strictness (meaning that the empty set is closed).

			a(0) = 1 counts the empty set, while a(1) = 2 counts {{1}} and {{},{1}}.
For a(2) = 1 the closure system is as follows:  {{1,2},{1},{2},{}}.
The a(3) = 4 inequivalent set-systems of closed sets are:
  {{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},{}}.

Dmitry I. Ignatov, Supporting iPython code for counting nonequivalent closure systems w.r.t. the T_1 separation axiom, Github repository
Eric Weisstein's World of Mathematics, Separation Axioms
Wikipedia, Separation Axiom

The number of all closure operators is given in A102896, while A193674 contains the number of all nonisomorphic ones.
For T_1 closure operators and their strict counterparts, see A334254 and A334255, respectively; the only difference is a(1).
Cf. A326960, A326961, A326979.

cp's OEIS Frontend

A326877 Number of connectedness systems covering n vertices without singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A334254 Number of closure operators on a set of n elements which satisfy the T_1 separation axiom.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A326900 Number of set-systems on n vertices that are closed under union and intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A326903 Number of set-systems (without {}) on n vertices that are closed under intersection and have an edge containing all of the vertices, or Moore families without {}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102499 Primes of the concatenated form 3nn3.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326874 BII-numbers of abstract simplicial complexes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326913 BII-numbers of set-systems (without {}) closed under union and intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334252 Number of closure operators on a set of n elements which satisfy the T_0 separation axiom.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions