A368095 - OEIS

A368095

Number of non-isomorphic set-systems of weight n satisfying a strict version of the axiom of choice.

1, 1, 2, 4, 8, 17, 39, 86, 208, 508, 1304

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

OFFSET

0,3

COMMENTS

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

LINKS

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

EXAMPLE

Non-isomorphic representatives of the a(1) = 1 through a(5) = 17 set-systems:

{1} {12} {123} {1234} {12345}

{1}{2} {1}{23} {1}{234} {1}{2345}

{2}{12} {12}{34} {12}{345}

{1}{2}{3} {13}{23} {14}{234}

{3}{123} {23}{123}

{1}{2}{34} {4}{1234}

{1}{3}{23} {1}{2}{345}

{1}{2}{3}{4} {1}{23}{45}

{1}{24}{34}

{1}{4}{234}

{2}{13}{23}

{2}{3}{123}

{3}{13}{23}

{4}{12}{34}

{1}{2}{3}{45}

{1}{2}{4}{34}

{1}{2}{3}{4}{5}

MATHEMATICA

Table[Length[Select[bmp[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 10}]

CROSSREFS

For labeled graphs we have A133686, complement A367867.

For unlabeled graphs we have A134964, complement A140637.

For set-systems we have A367902, complement A367903.

These set-systems have BII-numbers A367906, complement A367907.

The complement is A368094, connected A368409.

Repeats allowed: A368098, ranks A368100, complement A368097, ranks A355529.

Minimal multiset partitions not of this type are counted by A368187.

The connected case is A368410.

Factorizations of this type are counted by A368414, complement A368413.

Allowing repeated edges gives A368422, complement A368421.

A000110 counts set-partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A001055, A007717, A302545, A306005, A316983, A319560, A321194, A321405, A330223, A367769, A367901.

Sequence in context: A132043 A055545 A241671 * A036375 A036376 A000598

Adjacent sequences: A368092 A368093 A368094 * A368096 A368097 A368098

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 24 2023

STATUS

approved