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

Author

Don Knuth, Jul 01 2005

Keywords

• nonn
• hard
• nice
• more

Comments

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

Examples

			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)
		

References

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

Links

• 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

Crossrefs

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.

Formula

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

Extensions

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