A193675 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,1

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

REFERENCES

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

LINKS

Table of n, a(n) for n=0..7.

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

FORMULA

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

EXAMPLE

From Gus Wiseman, Aug 04 2019: (Start)

Non-isomorphic representatives of the a(0) = 2 through a(2) = 10 sets of sets:

{} {} {}

{{}} {{}} {{}}

{{},{1}} {{1,2}}

{{},{1}}

{{},{1,2}}

{{2},{1,2}}

{{},{2},{1,2}}

{{1},{2},{1,2}}

{{},{1},{2},{1,2}}

(End)

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.

Sequence in context: A370070 A109460 A108801 * A326904 A111022 A086852

Adjacent sequences: A193672 A193673 A193674 * A193676 A193677 A193678

KEYWORD

nonn,hard,nice,more

AUTHOR

Don Knuth, Jul 01 2005

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

STATUS

approved