A326907 -id:A326907 - 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

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

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

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

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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