OFFSET
0,5
COMMENTS
A multiset partition is normal if it covers an initial interval of positive integers. It is unsortable if no permutation has an ordered concatenation, or equivalently if the concatenation of its lexicographically-ordered parts is not weakly increasing. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.
EXAMPLE
The a(3) = 1 and a(4) = 17 multiset partitions:
{{1,3},{2}} {{1,1,3},{2}}
{{1,2},{1,2}}
{{1,2},{1,3}}
{{1,2,3},{2}}
{{1,2,4},{3}}
{{1,3},{2,2}}
{{1,3},{2,3}}
{{1,3},{2,4}}
{{1,3,3},{2}}
{{1,3,4},{2}}
{{1,4},{2,3}}
{{1},{1,3},{2}}
{{1},{2,4},{3}}
{{1,3},{2},{2}}
{{1,3},{2},{3}}
{{1,3},{2},{4}}
{{1,4},{2},{3}}
MATHEMATICA
lexsort[f_, c_]:=OrderedQ[PadRight[{f, c}]];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Sort[#, lexsort]&/@Join@@mps/@allnorm[n], !OrderedQ[Join@@#]&]], {n, 0, 5}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 19 2019
STATUS
approved