OFFSET
0,3
COMMENTS
A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition 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 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
Wikipedia, Axiom of choice.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions:
{{1}} {{1,1}} {{1,1,1}} {{1,1,1,1}}
{{1,2}} {{1,2,2}} {{1,1,2,2}}
{{1},{2}} {{1,2,3}} {{1,2,2,2}}
{{1},{2,2}} {{1,2,3,3}}
{{1},{2,3}} {{1,2,3,4}}
{{2},{1,2}} {{1},{1,2,2}}
{{1},{2},{3}} {{1,1},{2,2}}
{{1,2},{1,2}}
{{1},{2,2,2}}
{{1,2},{2,2}}
{{1},{2,3,3}}
{{1,2},{3,3}}
{{1},{2,3,4}}
{{1,2},{3,4}}
{{1,3},{2,3}}
{{2},{1,2,2}}
{{3},{1,2,3}}
{{1},{2},{3,3}}
{{1},{2},{3,4}}
{{1},{3},{2,3}}
{{1},{2},{3},{4}}
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], Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 6}]
CROSSREFS
These multiset partitions have ranks A368100.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Dec 25 2023
STATUS
approved