OFFSET
0,3
COMMENTS
A multiset is normal if it covers an initial interval of positive integers. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of (3,3,5,5,5,6) is (1,1,2,2,2,3).
A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}. For example, the (headless) combinatory separations of the multiset (1122) are (1122), (1)(112), (1)(122), (11)(11), (12)(12), (1)(1)(11), (1)(1)(12), (1)(1)(1)(1). This list excludes (12)(11), because one cannot partition (1122) into two blocks where one block has two distinct elements and the other has two equal elements.
EXAMPLE
The combinatory separations for n = 1, 3, 5, 9, 10, 13 (heads not shown):
(1) (12) (112) (1112) (1122) (1223)
(1)(1) (1)(11) (1)(111) (11)(11) (1)(112)
(1)(12) (1)(112) (1)(112) (11)(12)
(1)(1)(1) (11)(12) (1)(122) (1)(122)
(1)(1)(11) (12)(12) (1)(123)
(1)(1)(12) (1)(1)(11) (12)(12)
(1)(1)(1)(1) (1)(1)(12) (1)(1)(11)
(1)(1)(1)(1) (1)(1)(12)
(1)(1)(1)(1)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
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]]]];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]], i}, {i, Length[Union[m]]}];
ptnToNorm[y_]:=Join@@Table[ConstantArray[i, y[[i]]], {i, Length[y]}];
Table[Length[Union[Table[Sort[normize/@m], {m, mps[ptnToNorm[stc[n]]]}]]], {n, 0, 100}]
CROSSREFS
Multisets of compositions are A034691.
The described multiset is a row of A095684.
Combinatory separations of normal multisets are A269134.
Shuffles of compositions are counted by A292884.
Combinatory separations of prime indices are A318559.
The version for prime indices is A318560.
Combinatory separations of strongly normal multisets are A318563.
Multiset partitions of the described multiset are A333942.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Length of Lyndon factorization is A329312.
- Dealings are counted by A333939.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Apr 16 2020
STATUS
approved