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

0, 0, 1, 3, 12, 37, 133, 433, 1516, 5209, 18555

Offset

0,4

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

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

Wikipedia, Axiom of choice.

Example

Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 multiset partitions:
  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
             {{1},{1},{1}}  {{1,1},{1,1}}
             {{1},{2},{2}}  {{1},{1},{1,1}}
                            {{1},{1},{2,2}}
                            {{1},{1},{2,3}}
                            {{1},{2},{1,2}}
                            {{1},{2},{2,2}}
                            {{2},{2},{1,2}}
                            {{1},{1},{1},{1}}
                            {{1},{1},{2},{2}}
                            {{1},{2},{2},{2}}
                            {{1},{2},{3},{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]}]]];
Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 6}]

Crossrefs

The case of unlabeled graphs appears to be A140637, complement A134964.

These multiset partitions have ranks A355529.

The case of labeled graphs is A367867, complement A133686.

Set-systems not of this type are A367902, ranks A367906.

Set-systems of this type are A367903, ranks A367907.

For set-systems we have A368094, complement A368095.

The complement is A368098, ranks A368100, connected case A368412.

Minimal multiset partitions of this type are ranked by A368187.

The connected case is A368411.

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

For set multipartitions we have A368421, complement A368422.

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, A316983, A317533, A319616, A321405, A367905, A368409, A368410.

Sequence in context: A264423 A240193 A319077 * A008907 A048246 A320203

Adjacent sequences: A368094 A368095 A368096 * A368098 A368099 A368100

Keyword

nonn,more

Author

Gus Wiseman, Dec 25 2023

Status

approved