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. 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) = 11 multiset partitions:
{{1}} {{1,1}} {{1,1,1}} {{1,1,1,1}}
{{1,2}} {{1,2,2}} {{1,1,2,2}}
{{1,2,3}} {{1,2,2,2}}
{{2},{1,2}} {{1,2,3,3}}
{{1,2,3,4}}
{{1},{1,2,2}}
{{1,2},{1,2}}
{{1,2},{2,2}}
{{1,3},{2,3}}
{{2},{1,2,2}}
{{3},{1,2,3}}
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]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute /@ Select[mpm[n], Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 6}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Dec 26 2023
STATUS
approved