A368422 - OEIS

A368422

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

1, 1, 2, 4, 9, 18, 43, 95, 233, 569

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

OFFSET

0,3

COMMENTS

A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any sequence of nonempty sets, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.

LINKS

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

Wikipedia, Axiom of choice.

EXAMPLE

Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 set multipartitions:

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

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

{{1},{2},{3}} {{1,2},{3,4}} {{1,4},{2,3,4}}

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

{{3},{1,2,3}} {{4},{1,2,3,4}}

{{1},{2},{3,4}} {{1},{2,3},{2,3}}

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

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

{{1},{2,4},{3,4}}

{{1},{4},{2,3,4}}

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

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

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

{{4},{1,2},{3,4}}

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

{{1},{2},{4},{3,4}}

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

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];

Table[Length[Union[brute /@ Select[mpm[n], And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 6}]

CROSSREFS

The case of unlabeled graphs is A134964, complement A140637.

Set multipartitions have ranks A302478, cf. A073576.

The case of labeled graphs is A133686, complement A367867.

The complement without repeats is A368094 connected A368409.

Without repeats we have A368095, connected A368410.

The complement allowing repeats is A368097, ranks A355529.

Allowing repeated elements gives A368098, ranks A368100.

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

The complement is counted by 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. A302545, A306005, A317533, A318360, A367903.

Sequence in context: A032175 A000678 A362037 * A283877 A331850 A373808

Adjacent sequences: A368419 A368420 A368421 * A368423 A368424 A368425

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 26 2023

STATUS

approved