A102896 -id:A102896 - cp's OEIS frontend

A367916 Number of sets of nonempty subsets of {1..n} with the same number of edges as covered vertices.

1, 2, 6, 45, 1376, 161587, 64552473, 85987037645, 386933032425826, 6005080379837219319, 328011924848834642962619, 64153024576968812343635391868, 45547297603829979923254392040011994, 118654043008142499115765307533395739785599

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50

The covering case is A054780.
For graphs we have A367862, covering A367863, unlabeled A006649.
These set-systems have ranks A367917.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A136556 counts set-systems on {1..n} with n edges.
Cf. A092918, A102896, A133686, A306445, A323818, A355740, A367770, A367869, A367901, A367902, A367905.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]]], Length[Union@@#]==Length[#]&]],{n,0,3}]

\\ Here b(n) is A054780(n).
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(2^k-1, n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A054780.

A326882 Irregular triangle read by rows where T(n,k) is the number of finite topologies with n points and k nonempty open sets, 0 <= k <= 2^n - 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 1, 0, 1, 6, 9, 6, 6, 0, 1, 0, 1, 14, 43, 60, 72, 54, 54, 20, 24, 0, 12, 0, 0, 0, 1, 0, 1, 30, 165, 390, 630, 780, 955, 800, 900, 500, 660, 240, 390, 120, 190, 10, 100, 0, 60, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Aug 01 2019

			Triangle begins:
  1
  0  1
  0  1  2  1
  0  1  6  9  6  6  0  1
  0  1 14 43 60 72 54 54 20 24  0 12  0  0  0  1
Row n = 3 counts the following topologies:
{}{123} {}{1}{123}  {}{1}{12}{123} {}{1}{2}{12}{123}  {}{1}{2}{12}{13}{123}
        {}{2}{123}  {}{1}{13}{123} {}{1}{3}{13}{123}  {}{1}{2}{12}{23}{123}
        {}{3}{123}  {}{1}{23}{123} {}{2}{3}{23}{123}  {}{1}{3}{12}{13}{123}
        {}{12}{123} {}{2}{12}{123} {}{1}{12}{13}{123} {}{1}{3}{13}{23}{123}
        {}{13}{123} {}{2}{13}{123} {}{2}{12}{23}{123} {}{2}{3}{12}{23}{123}
        {}{23}{123} {}{2}{23}{123} {}{3}{13}{23}{123} {}{2}{3}{13}{23}{123}
                    {}{3}{12}{123}
                    {}{3}{13}{123}      {}{1}{2}{3}{12}{13}{23}{123}
                    {}{3}{23}{123}

Andrew Howroyd, Table of n, a(n) for n = 0..254
Wikipedia, Topological space

Row lengths are A000079.
Row sums are A000798.
Cf. A001930, A014466, A102894, A102895, A102896, A102897, A306445, A326876, A326878, A326881.
Columns: A281774 and refs therein.

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

Terms a(31) and beyond from Andrew Howroyd, Aug 10 2019

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

A326880 BII-numbers of set-systems that are closed under nonempty intersection.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 23, 24, 25, 26, 27, 29, 31, 32, 33, 34, 35, 38, 39, 40, 41, 42, 43, 46, 47, 56, 57, 58, 59, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 85, 87, 88

Offset: 1

Gus Wiseman, Jul 29 2019

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.

The enumeration of these set-systems by number of covered vertices is A326881.

			Most small numbers are in the sequence, but the sequence of non-terms together with the set-systems with those BII-numbers begins:
  20: {{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  28: {{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  36: {{1,2},{2,3}}
  37: {{1},{1,2},{2,3}}
  44: {{1,2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  48: {{1,3},{2,3}}
  49: {{1},{1,3},{2,3}}
  50: {{2},{1,3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  84: {{1,2},{1,3},{1,2,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..10000

Cf. A006126, A048793, A102894, A102895, A102896, A102897, A306445, A326031, A326872, A326874, A326875, A326876, A326881.

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

from itertools import count, islice, combinations
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen():
    for n in count(0):
        E,f = [bin_i(k) for k in bin_i(n)],0
        for i in combinations(E,2):
            x = list(set(i[0])&set(i[1]))
            if x not in E and len(x) > 0:
                f += 1
                break
        if f < 1:
            yield n
A326880_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Mar 07 2025

A326881 Number of set-systems with {} that are closed under intersection and cover n vertices.

Original entry on oeis.org

1, 1, 5, 71, 4223, 2725521, 151914530499, 28175294344381108057

Offset: 0

Gus Wiseman, Jul 30 2019

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

The case also closed under union is A000798.
The connected case (i.e., with maximum) is A102894.
The same for union instead of intersection is (also) A102894.
The non-covering case is A102895.
The BII-numbers of these set-systems (without the empty set) are A326880.
The unlabeled case is A326883.
Cf. A003465, A014466, A102896, A102897, A193674, A193675, A306445, A307249, A326878.

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

Inverse binomial transform of A102895. - Andrew Howroyd, Aug 10 2019

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

A367772 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice in more than one way.

Original entry on oeis.org

0, 0, 1, 23, 1105, 154941, 66072394, 88945612865, 396990456067403

Offset: 0

Gus Wiseman, Dec 12 2023

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			Non-isomorphic representatives of the a(3) = 23 set-systems:
  {{1,2}}
  {{1,2,3}}
  {{1},{2,3}}
  {{1},{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

Wikipedia, Axiom of choice.

For at least one choice we have A367902.
For no choices we have A367903, no singletons A367769, ranks A367907.
For a unique choice we have A367904, ranks A367908.
These set-systems have ranks A367909.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
Cf. A059201, A102896, A133686, A283877, A306445, A323818, A355741, A367770, A367862, A367869, A367901, A367905.

Table[Length[Select[Subsets[Subsets[Range[n]]], Length[Select[Tuples[#], UnsameQ@@#&]]>1&]], {n,0,3}]

A367903(n) + A367904(n) + a(n) = A058891(n).

a(5)-a(8) from Christian Sievers, Jul 26 2024

A326906 Number of sets of subsets of {1..n} that are closed under union and cover all n vertices.

Original entry on oeis.org

2, 2, 8, 90, 4542, 2747402, 151930948472, 28175295407840207894

Offset: 0

Gus Wiseman, Aug 03 2019

Differs from A102895 in having a(0) = 2 instead of 1.

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

The case without empty sets is A102894.
The case with a single covering edge is A102895.
Binomial transform is A102897.
The case also closed under intersection is A326878 for n > 0.
The same for intersection instead of union is (also) A326906.
The unlabeled version is A326907.
Cf. A000798, A102896, A102897, A108800, A193675, A306445, A326880, A326881, A326883.

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

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

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

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

cp's OEIS Frontend

A367916 Number of sets of nonempty subsets of {1..n} with the same number of edges as covered vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A326882 Irregular triangle read by rows where T(n,k) is the number of finite topologies with n points and k nonempty open sets, 0 <= k <= 2^n - 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A326870 Number of connectedness systems covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A326880 BII-numbers of set-systems that are closed under nonempty intersection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A326881 Number of set-systems with {} that are closed under intersection and cover n vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A367772 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice in more than one way.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326906 Number of sets of subsets of {1..n} that are closed under union and cover all n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326869 Number of unlabeled connected connectedness systems on n vertices.

Views

Author

Keywords