login
A368411
Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.
7
0, 0, 1, 2, 6, 15, 50, 148, 509, 1725, 6218
OFFSET
0,4
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.
EXAMPLE
Non-isomorphic representatives of the a(2) = 1 through a(5) = 15 multiset partitions:
{{1},{1}} {{1},{1,1}} {{1},{1,1,1}} {{1},{1,1,1,1}}
{{1},{1},{1}} {{1,1},{1,1}} {{1,1},{1,1,1}}
{{1},{1},{1,1}} {{1},{1},{1,1,1}}
{{1},{2},{1,2}} {{1},{1,1},{1,1}}
{{2},{2},{1,2}} {{1},{1},{1,2,2}}
{{1},{1},{1},{1}} {{1},{1,2},{2,2}}
{{1},{2},{1,2,2}}
{{2},{1,2},{1,2}}
{{2},{1,2},{2,2}}
{{2},{2},{1,2,2}}
{{3},{3},{1,2,3}}
{{1},{1},{1},{1,1}}
{{1},{2},{2},{1,2}}
{{2},{2},{2},{1,2}}
{{1},{1},{1},{1},{1}}
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
The case of labeled graphs is A140638, connected case of A367867.
The complement for labeled graphs is A129271, connected case of A133686.
This is the connected case of A368097.
For set-systems we have A368409, connected case of A368094, ranks A367907.
Compliment set-systems: A368410, connected case of A368095, ranks A367906.
The complement is A368412, connected case of A368098, ranks A368100.
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.
Sequence in context: A291848 A363207 A196961 * A255540 A323926 A256982
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Dec 26 2023
STATUS
approved