login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.
7

%I #7 Dec 26 2023 20:32:48

%S 0,0,1,2,6,15,50,148,509,1725,6218

%N Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.

%C 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.

%C 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.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of choice</a>.

%e Non-isomorphic representatives of the a(2) = 1 through a(5) = 15 multiset partitions:

%e {{1},{1}} {{1},{1,1}} {{1},{1,1,1}} {{1},{1,1,1,1}}

%e {{1},{1},{1}} {{1,1},{1,1}} {{1,1},{1,1,1}}

%e {{1},{1},{1,1}} {{1},{1},{1,1,1}}

%e {{1},{2},{1,2}} {{1},{1,1},{1,1}}

%e {{2},{2},{1,2}} {{1},{1},{1,2,2}}

%e {{1},{1},{1},{1}} {{1},{1,2},{2,2}}

%e {{1},{2},{1,2,2}}

%e {{2},{1,2},{1,2}}

%e {{2},{1,2},{2,2}}

%e {{2},{2},{1,2,2}}

%e {{3},{3},{1,2,3}}

%e {{1},{1},{1},{1,1}}

%e {{1},{2},{2},{1,2}}

%e {{2},{2},{2},{1,2}}

%e {{1},{1},{1},{1},{1}}

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

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

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

%t 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]]]]]]]]];

%t Table[Length[Union[brute /@ Select[mpm[n],Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,6}]

%Y The case of labeled graphs is A140638, connected case of A367867.

%Y The complement for labeled graphs is A129271, connected case of A133686.

%Y This is the connected case of A368097.

%Y For set-systems we have A368409, connected case of A368094, ranks A367907.

%Y Compliment set-systems: A368410, connected case of A368095, ranks A367906.

%Y The complement is A368412, connected case of A368098, ranks A368100.

%Y A000110 counts set partitions, non-isomorphic A000041.

%Y A003465 counts covering set-systems, unlabeled A055621.

%Y A007716 counts non-isomorphic multiset partitions, connected A007718.

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

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

%Y Cf. A140637, A302545, A316983, A317533, A319616, A367903, A367905, A368187.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Dec 26 2023