A102895 -id:A102895 - cp's OEIS frontend

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

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

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

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

Original entry on oeis.org

1, 1, 4, 22, 302, 28630, 216533404, 5592325966377736

Offset: 0

Gus Wiseman, Jul 30 2019

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 22 set-systems:
  {{}}  {{}{1}}  {{}{12}}        {{}{123}}
                 {{}{1}{2}}      {{}{1}{23}}
                 {{}{2}{12}}     {{}{3}{123}}
                 {{}{1}{2}{12}}  {{}{1}{2}{3}}
                                 {{}{23}{123}}
                                 {{}{1}{3}{23}}
                                 {{}{2}{3}{123}}
                                 {{}{3}{13}{23}}
                                 {{}{1}{23}{123}}
                                 {{}{3}{23}{123}}
                                 {{}{1}{2}{3}{23}}
                                 {{}{1}{2}{3}{123}}
                                 {{}{2}{3}{13}{23}}
                                 {{}{1}{3}{23}{123}}
                                 {{}{2}{3}{23}{123}}
                                 {{}{3}{13}{23}{123}}
                                 {{}{1}{2}{3}{13}{23}}
                                 {{}{1}{2}{3}{23}{123}}
                                 {{}{2}{3}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}}
                                 {{}{1}{2}{3}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}{123}}

The case also closed under union is A001930.
The connected case (i.e., with maximum) is A108798.
The same for union instead of intersection is (also) A108798.
The non-covering case is A108800.
The labeled case is A326881.
Cf. A000798, A102894, A102895, A102897, A193674, A193675, A306445, A326875, A326878, A326880.

a(n) = A108800(n) - A108800(n-1) for n > 0. - Andrew Howroyd, Aug 10 2019

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

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

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

Original entry on oeis.org

1, 2, 4, 10, 38, 368, 29328, 216591692, 5592326399531792

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.

Apart from the offset the same as A193675. - R. J. Mathar, Aug 09 2019

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

The covering case is A108800(n - 1).
The case with an edge containing all of the vertices is A193674(n - 1).
The case with union instead of intersection is A193674.
The labeled version is A326901.
Cf. A000798, A001930, A006058, A102895, A102898, A326876, A326866, A326878, A326882, A326903, A326906.

a(n > 0) = 2 * A193674(n - 1).

A326907 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and cover all n vertices. First differences of A193675.

Original entry on oeis.org

2, 2, 6, 28, 330, 28960, 216562364, 5592326182940100

Offset: 0

Gus Wiseman, Aug 03 2019

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

			Non-isomorphic representatives of the a(0) = 2 through a(3) = 28 sets of sets:
  {}    {{1}}    {{12}}          {{123}}
  {{}}  {{}{1}}  {{}{12}}        {{}{123}}
                 {{2}{12}}       {{3}{123}}
                 {{}{2}{12}}     {{23}{123}}
                 {{1}{2}{12}}    {{}{3}{123}}
                 {{}{1}{2}{12}}  {{}{23}{123}}
                                 {{1}{23}{123}}
                                 {{3}{23}{123}}
                                 {{13}{23}{123}}
                                 {{}{1}{23}{123}}
                                 {{}{3}{23}{123}}
                                 {{}{13}{23}{123}}
                                 {{2}{3}{23}{123}}
                                 {{2}{13}{23}{123}}
                                 {{3}{13}{23}{123}}
                                 {{12}{13}{23}{123}}
                                 {{}{2}{3}{23}{123}}
                                 {{}{2}{13}{23}{123}}
                                 {{}{3}{13}{23}{123}}
                                 {{}{12}{13}{23}{123}}
                                 {{2}{3}{13}{23}{123}}
                                 {{3}{12}{13}{23}{123}}
                                 {{}{2}{3}{13}{23}{123}}
                                 {{}{3}{12}{13}{23}{123}}
                                 {{2}{3}{12}{13}{23}{123}}
                                 {{}{2}{3}{12}{13}{23}{123}}
                                 {{1}{2}{3}{12}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}{123}}

The case without empty sets is A108798.
The case with a single covering edge is A108800.
First differences of A193675.
The case also closed under intersection is A326898 for n > 0.
The labeled version is A326906.
The same for union instead of intersection is (also) A326907.
Cf. A001930, A102895, A108798, A193674, A193675, A326880, A326881, A326883, A326898, A326908.

a(7) added from A108800 by Andrew Howroyd, Aug 10 2019

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

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

Original entry on oeis.org

1, 1, 3, 19, 319, 21881, 16417973, 1063459099837, 225402359008808647339

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(0) = 1 through a(3) = 19 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,3}}
                          {{2},{1,2},{2,3}}
                          {{3},{1,3},{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}}

The case closed under union and intersection is A006058.
The case with union instead of intersection is A102894.
The unlabeled version is A108800(n - 1).
The non-covering case is A326901.
The connected case is A326903.
Cf. A000798, A001930, A102895, A102898, A182507, A326866, A326876, A326878, A326882, A326900, A326901, A326904.

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

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

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

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

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Examples

Crossrefs

Formula

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326907 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and cover all n vertices. First differences of A193675.

Views

Author

Keywords

Comments

Examples

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

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

Views