login
A326211
Number of unsortable normal multiset partitions of weight n.
18
0, 0, 0, 1, 17, 170, 1455, 11678, 92871, 752473
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.
FORMULA
A255906(n) = a(n) + A326212(n).
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
Unsortable set partitions are A058681.
Sortable normal multiset partitions are A326212.
Non-crossing normal multiset partitions are A324171.
MM-numbers of unsortable multiset partitions are A326258.
Sequence in context: A282922 A023015 A022645 * A164747 A166579 A142169
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 19 2019
STATUS
approved