A368422 Number of non-isomorphic set multipartitions of weight n satisfying a strict version of the axiom of choice.

1, 1, 2, 4, 9, 18, 43, 95, 233, 569

Offset: 0

Author

Gus Wiseman, Dec 26 2023

Keywords

• nonn
• more

Comments

A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition 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 sequence of nonempty sets, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.

Examples

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 set multipartitions:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}        {{1,2,3,4,5}}
         {{1},{2}}  {{1},{2,3}}    {{1,2},{1,2}}      {{1},{2,3,4,5}}
                    {{2},{1,2}}    {{1},{2,3,4}}      {{1,2},{3,4,5}}
                    {{1},{2},{3}}  {{1,2},{3,4}}      {{1,4},{2,3,4}}
                                   {{1,3},{2,3}}      {{2,3},{1,2,3}}
                                   {{3},{1,2,3}}      {{4},{1,2,3,4}}
                                   {{1},{2},{3,4}}    {{1},{2,3},{2,3}}
                                   {{1},{3},{2,3}}    {{1},{2},{3,4,5}}
                                   {{1},{2},{3},{4}}  {{1},{2,3},{4,5}}
                                                      {{1},{2,4},{3,4}}
                                                      {{1},{4},{2,3,4}}
                                                      {{2},{1,3},{2,3}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{4},{1,2},{3,4}}
                                                      {{1},{2},{3},{4,5}}
                                                      {{1},{2},{4},{3,4}}
                                                      {{1},{2},{3},{4},{5}}
		

Links

• Wikipedia, Axiom of choice.

Crossrefs

The case of unlabeled graphs is A134964, complement A140637.

Set multipartitions have ranks A302478, cf. A073576.

The case of labeled graphs is A133686, complement A367867.

The complement without repeats is A368094 connected A368409.

Without repeats we have A368095, connected A368410.

The complement allowing repeats is A368097, ranks A355529.

Allowing repeated elements gives A368098, ranks A368100.

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

The complement is counted by A368421.

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, A306005, A317533, A318360, A367903.

Programs

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],And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]