A326949 -id:A326949 - cp's OEIS frontend

A326947 BII-numbers of T_0 set-systems.

0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 69, 70, 71, 73, 74, 75, 77, 78

Offset: 1

Gus Wiseman, Aug 08 2019

The dual of a set-system has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated 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 sequence of all T_0 set-systems together with their BII numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  17: {{1},{1,3}}
  19: {{1},{2},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}

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

T_0 set-systems are counted by A326940, with unlabeled version A326946.

Cf. A059201, A316978, A319559, A319564, A326939, A326941, A326949.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
TZQ[sys_]:=UnsameQ@@dual[sys];
Select[Range[0,100],TZQ[bpe/@bpe[#]]&]

from itertools import count, chain, islice
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):
        a,b,s = [bin_i(k) for k in bin_i(n)],[],set()
        for i in {i for i in chain.from_iterable(a)}:
            b.append([])
            for j in range(len(a)):
                if i in a[j]:
                    b[-1].append(j)
            s.add(tuple(b[-1]))
        if len(s) == len(b):
            yield n
A326947_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Jul 25 2024

A326946 Number of unlabeled T_0 set-systems on n vertices.

Original entry on oeis.org

1, 2, 5, 34, 1919, 18660178

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

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

The non-T_0 version is A000612.
The antichain case is A245567.
The covering case is A319637.
The labeled version is A326940.
The version with empty edges allowed is A326949.
Cf. A003180, A055621, A059052, A059201, A316978, A319559, A319564, A326942.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Union[normclut/@Select[Subsets[Subsets[Range[n],{1,n}]],UnsameQ@@dual[#]&]]],{n,0,3}]

Partial sums of A319637.

a(n) = A326949(n)/2.

a(5) from Max Alekseyev, Oct 11 2023

A326940 Number of T_0 set-systems on n vertices.

Original entry on oeis.org

1, 2, 7, 112, 32105, 2147161102, 9223372004645756887, 170141183460469231537996491362807709908, 57896044618658097711785492504343953921871039195927143534469727707459805807105

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			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}}

The non-T_0 version is A058891 shifted to the left.
The covering case is A059201.
The version with empty edges is A326941.
The unlabeled version is A326946.
Cf. A003180, A316978, A319559, A319564, A319637, A326939, A326947, A326949.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],UnsameQ@@dual[#]&]],{n,0,3}]

Binomial transform of A059201.

A326941 Number of T_0 sets of subsets of {1..n}.

Original entry on oeis.org

2, 4, 14, 224, 64210, 4294322204, 18446744009291513774, 340282366920938463075992982725615419816, 115792089237316195423570985008687907843742078391854287068939455414919611614210

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

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

The non-T_0 version is A001146.
The covering case is A326939.
The case without empty edges is A326940.
The unlabeled version is A326949.
Cf. A003180, A059201, A316978, A319559, A319564, A319637, A326946, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],UnsameQ@@dual[#]&]],{n,0,3}]

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

Binomial transform of A326939.

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

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Original entry on oeis.org

2, 1, 1, 5, 76, 5993, 7689745, 2414465044600, 56130437141763247212112, 286386577668298408602599478477358234902247

Offset: 0

Patrick De Causmaecker, Jul 25 2014

This is the number of antichain covers such that the induced partition contains only singletons. The induced partition of {{1,2},{2,3},{1,3},{3,4}} is {{1},{2},{3},{4}}, while the induced partition of {{1,2,3},{2,3,4}} is {{1},{2,3},{4}}.
This sequence is related to A006126. See 1st formula.
The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
Sets of subsets of the described type are said to be T_0. - Gus Wiseman, Aug 14 2019

			For n = 0, a(0) = 2 by the antisets {}, {{}}.
For n = 1, a(1) = 1 by the antiset {{1}}.
For n = 2, a(2) = 1 by the antiset {{1},{2}}.
For n = 3, a(3) = 5 by the antisets {{1},{2},{3}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1,2},{1,3},{2,3}}.

Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).
Sequences counting and ranking T_0 structures:
  A000112 (unlabeled topologies),
  A001035 (topologies),
  A059201 (covering set-systems),
  A245567 (antichain covers),
  A309615 (covering set-systems closed under intersection),
  A316978 (factorizations),
  A319559 (unlabeled set-systems by weight),
  A319564 (integer partitions),
  A319637 (unlabeled covering set-systems),
  A326939 (covering sets of subsets),
  A326940 (set-systems),
  A326941 (sets of subsets),
  A326943 (covering sets of subsets closed under intersection),
  A326944 (covering sets of subsets with {} and closed under intersection),
  A326945 (sets of subsets closed under intersection),
  A326946 (unlabeled set-systems),
  A326947 (BII-numbers of set-systems),
  A326948 (connected set-systems),
  A326949 (unlabeled sets of subsets),
  A326950 (antichains),
  A326959 (set-systems closed under intersection),
  A327013 (unlabeled covering set-systems closed under intersection),
  A327016 (BII-numbers of topologies).

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 14 2019 *)

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
a(n) = A006126(n) - Sum_{k=1..n-1} S(n,k)*a(k).
Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
Inverse binomial transform of A326950, if we assume a(0) = 1. - Gus Wiseman, Aug 14 2019

Definition corrected by Patrick De Causmaecker, Oct 10 2014

a(9), based on A000372, from Patrick De Causmaecker, Jun 01 2023

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Original entry on oeis.org

2, 4, 8, 40, 2464

Offset: 0

Gus Wiseman, Aug 13 2019

Alternatively, these are unlabeled sets of subsets of {1..n} whose dual is a (strict) antichain, also called T_1 sets of subsets. The dual of a set of subsets has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. An antichain is a set of subsets where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 8 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{},{1}}
                  {{1},{2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Unlabeled sets of subsets are A003180.
Unlabeled T_0 sets of subsets are A326949.
The labeled version is A326967.
The case without empty edges is A326972.
The covering case is A327011 (first differences).
Cf. A003181, A059052, A326960, A326965, A326969, A326974, A326976.

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

a(n) = Sum_{k = 0..n} A327011(k).

A326942 Number of unlabeled T_0 sets of subsets of {1..n} that cover all n vertices.

Original entry on oeis.org

2, 2, 6, 58, 3770

Offset: 0

Gus Wiseman, Aug 07 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			Non-isomorphic representatives of the a(0) = 2 through a(2) = 6 sets of subsets:
  {}    {{1}}     {{1},{2}}
  {{}}  {{},{1}}  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

The non-T_0 version is A003181.
The case without empty edges is A319637.
The labeled version is A326939.
The non-covering version is A326949 (partial sums).
Cf. A000371, A003180, A055621, A059201, A316978, A319559, A319564, A326907, A326941, A326943, A326946.

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

cp's OEIS Frontend

A326947 BII-numbers of T_0 set-systems.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A326946 Number of unlabeled T_0 set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326940 Number of T_0 set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326941 Number of T_0 sets of subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326951 Number of unlabeled sets of subsets of {1..n} where every covered vertex is the unique common element of some subset of the edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326942 Number of unlabeled T_0 sets of subsets of {1..n} that cover all n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula