A326908 -id:A326908 - cp's OEIS frontend

A193675 Number of nonisomorphic systems enumerated by A102897; that is, the number of inequivalent Horn functions, under permutation of variables.

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

Offset: 0

Don Knuth, Jul 01 2005

When speaking of inequivalent Boolean functions, three groups of symmetries are typically considered: Complementations only, the Abelian group (2,...,2) of 2^n elements; permutations only, the symmetric group of n! elements; or both complementations and permutations, the octahedral group of 2^n n! elements. In this case only symmetry with respect to the symmetric group is appropriate because complementation affects the property of being a Horn function.

Also the number of non-isomorphic sets of subsets of {1..n} that are closed under union. - Gus Wiseman, Aug 04 2019

			From _Gus Wiseman_, Aug 04 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(2) = 10 sets of sets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{1,2}}
                  {{},{1}}
                  {{},{1,2}}
                  {{2},{1,2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.

P. Colomb, A. Irlande and O. Raynaud, Counting of Moore Families for n=7, International Conference on Formal Concept Analysis (2010).
D. E. Knuth, HORN-COUNT

The covering case is A326907.
The case without {} is A193674.
The labeled version is A102897.
The same with intersection instead of union is also A193675.
The case closed under both union and intersection also is A326908.
Cf. A102894, A102895, A102896, A102897, A108798, A108800, A326867, A326875, A326904.

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

a(6) received from Don Knuth, Aug 17 2005
a(6) corrected by Pierre Colomb, Aug 02 2011
a(7) = 2*A193674(7) from Hugo Pfoertner, Jun 18 2018

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

A326909 Number of sets of subsets of {1..n} closed under union and intersection and covering all of the vertices.

Original entry on oeis.org

2, 2, 7, 45, 500, 9053, 257151, 11161244, 725343385, 69407094565, 9639771895398, 1919182252611715, 541764452276876719, 214777343584048313318, 118575323291814379721651, 90492591258634595795504697, 94844885130660856889237907260, 135738086271526574073701454370969, 263921383510041055422284977248713291

Offset: 0

Gus Wiseman, Aug 04 2019

nonn

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

			The a(0) = 2 through a(2) = 7 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}}

Covering sets of subsets are A000371.
The case without empty sets is A108798.
The case with a single covering edge is A326878.
The unlabeled version is A326898 for n > 0.
The case closed only under union is A326906.
The case closed only under intersection is (also) A326906.
Cf. A000798, A001930, A003465, A006058, A306445, A326876, A326882, A326907, A326908.

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

a(n) = A000798(n) + A006058(n). - Jean-François Alcover, Dec 30 2019, after Gus Wiseman's comment in A006058.

a(18) from A000798+A006058 by Jean-François Alcover, Dec 30 2019

cp's OEIS Frontend

A193675 Number of nonisomorphic systems enumerated by A102897; that is, the number of inequivalent Horn functions, under permutation of variables.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

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

A326909 Number of sets of subsets of {1..n} closed under union and intersection and covering all of the vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions